\documentclass[onecolumn,10pt]{article}
\usepackage{url}
\usepackage{epsfig}
\usepackage{amsmath}

% \setlength{\textheight}{9.0in} %.
% \setlength{\columnsep}{2.0pc} %.
\setlength{\textwidth}{6.5in} %.
% \setlength{\topmargin}{0.in} %.
% \setlength{\headheight}{0.0in} %.
% \setlength{\headsep}{0.0in} %.
\setlength{\oddsidemargin}{0in} %.
\setlength{\parindent}{1pc} %.


\newcommand{\comb}[2]{\binom{#1}{#2}}
\newcommand{\tronly}[1]{}
\newcommand{\comment}[1]{}

\begin{document}
% \include{trcover}

\title{Jerasure: A Library in C/C++ Facilitating Erasure Coding for Storage Applications \\
\mbox{}\\
Version 1.2}

\author{James S. Plank\thanks{{\tt plank@cs.utk.edu} or {\tt plank@eecs.utk.edu}, 865-974-4397,
This material
is based upon work supported by the National Science
Foundation under grant CNS-0615221.} \and Scott Simmerman \and Catherine D. Schuman}

\date{}

\pagenumbering{arabic}
\maketitle

\begin{center}
Technical Report CS-08-627\\
Department of Electrical Engineering and Computer Science \\
University of Tennessee\\
Knoxville, TN 37996 \\
\mbox{} \\
\url{http://www.cs.utk.edu/~plank/plank/papers/CS-08-627.html} \\
\mbox{} \\
This describes revision 1.2 of the code.
% \mbox{} \\
% Revision as of 
% Tue Aug 19 13:28:07 EDT 2008
\end{center}

\begin{abstract}
\input{abstract}
\end{abstract}

\pagestyle{headings}
\section*{If You Use This Library or Document}

Please send me an email to let me know how it goes.  One of the ways in which I
am evaluated both internally and externally is by the impact of my work, and if
you have found this library and/or this document useful, 
I would like to be able to document it.
Please send mail to {\em plank@eecs.utk.edu}.

The library itself is protected by the GNU LGPL.  It is free to use and modify
within the bounds of the LGPL.  None of the techniques implemented in this library
have been patented.

\subsection*{Finding the Code}

Please see
\url{http://www.cs.utk.edu/~plank/plank/papers/CS-08-627.html} to get the
TAR file for this code.

\newpage
\tableofcontents
\newpage

\section{Introduction}
\label{sec:intro}

Erasure coding for storage applications is growing in importance as storage
systems grow in size and complexity.  This paper describes {\bf jerasure}, a
library in C/C++ that supports erasure coding applications.  {\bf Jerasure}
has been designed to be modular, fast and flexible.  It is our hope that
storage designers and programmers will find {\bf jerasure} to be a 
convenient tool to add fault tolerance to their storage systems.

{\bf Jerasure} supports a {\em horizontal} mode of erasure codes.  We
assume that we have~$k$ devices that hold data.  To
that, we will add~$m$ devices whose contents will be calculated from 
the original~$k$ devices.  If the erasure code is a {\em Maximum Distance
Separable (MDS)} code, then the entire system will be able to tolerate
the loss of any~$m$ devices.  

\begin{figure}[ht]
\begin{center}
\begin{tabular}{c|c}
\epsfig{figure=Encoding.eps,width=3in} & 
\epsfig{figure=Decoding.eps,width=3in} \\
(a) Encoding. & (b) Decoding. \\
\end{tabular}
\caption{\label{fig:encoding} The act of {\em encoding} takes the contents of~$k$
data devices and encodes them on~$m$ coding devices.  The act of {\em decoding}
takes some subset of the collection of~$(k+m)$ total devices and from them 
recalcalates the original~$k$ devices of data.}
\end{center}
\end{figure}

As depicted in Figure~\ref{fig:encoding}, the act of encoding takes the original~$k$
data devices, and from them calculates~$m$ coding devices.  The act of decoding
takes the collection of~$(k+m)$ devices with erasures, and from the surviving 
devices recalculates the contents of the original~$k$ data devices.

Most codes have a third parameter~$w$, which is the {\em word size}.  The
description of a code views each device as having~$w$ bits worth of data.
The data devices are denoted~$D_0$ through~$D_{k-1}$ and the coding devices
are denoted~$C_0$ through~$C_{m-1}$.  Each device~$D_i$ or~$C_j$ holds~$w$
bits, denoted~$d_{i,0}, \ldots d_{i,w-1}$ and~$c_{i,0}, \ldots c_{i,w-1}$.
In reality of course, devices hold megabytes of data.  To map the description
of a code to its realization in a real system, we do one of two things:

\begin{enumerate}
\item When~$w \in \{ 8, 16, 32 \}$, we can consider each collection of~$w$
bits to be a byte, short word or word respectively.  Consider the case when~$w=8$.
We may view each device to hold~$B$ bytes.  The first byte of each coding
device will be encoded with the first byte of each data device.  The second
byte of each coding
device will be encoded with the second byte of each data device.  And so on.
This is how Standard Reed-Solomon coding works, and it should be clear how
it works when~$w = 16$ or $w = 32$.
\item Most other codes work by defining each coding bit~$c_{i,j}$ to be the
bitwise exclusive-or (XOR) of some subset of the other bits.  To implement
these codes in a real system, we assume that the device is composed of~$w$
{\em packets} of equal size.  
Now each packet is calculated to be the bitwise exclusive-or of some subset of
the other packets.  In this way, we can take advantage of the fact that we
can perform XOR operations on whole computer words rather than on bits.

The process is illustrated in Figure~\ref{fig:packets}.  In this figure,
we assume that~$k=4$, $m=2$ and $w=4$.  Suppose that a code is defined
such that coding bit~$c_{1,0}$ is goverened by the equation:
\[ c_{1,0} = d_{0,0} \oplus d_{1,1} \oplus d_{2,2} \oplus d_{3,3}, \]
where~$\oplus$ is the XOR operation.  Figure~\ref{fig:packets} shows how
the coding packet corresponding to~$c_{1,0}$ is calculated from the 
data packets corresponding to 
$d_{0,0}$, $d_{1,1}$, $d_{2,2}$ and $d_{3,3}.$  We call the size of each
packet the {\em packet size}, and the size of~$w$ packets to be the {\em
coding block size}.   The packetsize must be a multiple of 8 so obviously, the coding block size will be a multiple of
$w * packetsize$.
\end{enumerate}

\begin{figure}[ht]
\begin{center}
\epsfig{figure=Packets.eps,width=3in} \\
\caption{\label{fig:packets} Although codes are described on systems of~$w$
bits, their implementation employs {\em packets} that are much larger.  Each
packet in the implementation corresponds to a bit of the description.  This
figure is showing how the equation $c_{1,0} = d_{0,0} \oplus d_{1,1} \oplus d_{2,2} \oplus d_{3,3}$
is realized in an implementation.}
\end{center}
\end{figure}

\section{The Modules of the Library}

This library is broken into four modules, each with its own header file and implementation
in C++.  Typically, when using a code, one only needs three of these modules: {\bf galois},
{\bf jerasure} and one of the others.  The modules are:

\begin{enumerate}
\item {\bf galois.h/galois.cpp}: These are procedures for Galois Field Arithmetic
as described and implemented in~\cite{p:07:gfl}.
\item {\bf jerasure.h/jer\_$*$.cpp}: These are kernel routines that are common to
most erasure codes.  They do not depend on any module other than {\bf galois}.  
They include support
for matrix-based coding and decoding, bit-matrix-based coding and decoding, conversion
of bit-matrices to schedules, matrix and bit-matrix inversion.
\item {\bf reedsol.h/reedsol.cpp}: These are procedures for creating distribution matrices for Reed-Solomon coding~\cite{rs:60:pc,p:97:rs,pd:05:rs}, including Cauchy Reed-Solomon coding~/cite{bkk:95:xor,px:06:ocr}.  
They also include the optimized version of Reed-Solomon 
encoding for RAID-6 as discussed in~\cite{a:07:mr6}.
\item {\bf bitmatrices.h/bitmatrices.cpp}: These are procedures for performing RAID-6 coding and decoding with minimal density MDS codes -- the RAID-6 Liberation codes~\cite{p:08:lib}, Blaum-Roth codes~\cite{br:99:old} and the RAID-6 Liber8tion code~\cite{p:08:md8}. There are also procedures for performing generalized EVENODD and generalized RDP coding.
\end{enumerate}

Each module is described in its own section below.  Additionally, there are example programs
that show the usage of each module.  

\section{Matrix-Based Coding In General}
\label{sec:mbc}

The mechanics of matrix-based coding are explained in great detail in~\cite{p:97:rs}.  
We give a high-level overview here.

\begin{quote}
{\em {\bf Authors' Caveat:} We are using old nomenclature of ``distribution matrices.''
In standard coding theory, the ``distribution matrix'' is the transpose of the Generator
matrix.  In the next revision of {\bf jerasure}, we will update the nomenclature to
be more consistent with classic coding theory.}
\end{quote}

Suppose we have~$k$ data words and~$m$ coding words, each composed of~$w$ bits.  We can
describe the state of a matrix-based coding system by a matrix-vector product as
depicted in Figure~\ref{fig:matrix}.  The matrix is called a {\em distribution matrix}
and is a~$(k+m) \times k$ matrix.  The elements of the matrix are numbers in~$GF(2^w)$ for some
value of~$w$.  This means that they are integers between 0 and~$2^w-1$, and arithmetic
is performed using Galois Field arithmetic: addition is equal to XOR, and multiplication
is implemented in a variety of ways.  The Galois Field arithmetic library in~\cite{p:07:gfl}
has procedures which implement Galois Field arithmetic.

\begin{figure}[ht]
\begin{center}
\epsfig{figure=Matrix.eps,width=3in} \\
\caption{\label{fig:matrix} Using a matrix-vector product to describe a coding
system.}
\end{center}
\end{figure}

The top~$k$ rows of the distribution matrix compsose a~$k \times k$
identity matrix.  The remaining~$m$ rows are called the {\em coding
matrix}, and are defined in a variety of
ways~\cite{mor:89:edi,p:89:hdr,bkk:95:xor,pd:05:rs}.  The distribution matrix is
multiplied by a vector that contains the data words and yields a
product vector containing both the data and the coding words.  
Therefore, to encode, we need to perform~$m$ dot products of the coding 
matrix with the data.

To decode, we note that each word in the system has a corresponding
row of the distribution matrix.  When devices fail, we create a decoding
matrix from~$k$ rows of the distribution that correspond to non-failed
devices.  Note that this matrix multiplied by the original data equals
the~$k$ survivors whose rows we selected.  If we invert this matrix and
multiply it by both sides of the equation, then we are given a decoding
equation -- the inverted matrix multiplied by the survivors equals the
original data.  

\section{Bit-Matrix Coding In General}

Bit-matrix coding is first described in the original Cauchy Reed-Solomon
coding paper~\cite{bkk:95:xor}.  To encode and decode with a bit-matrix, we expand a 
distribution matrix in~$GF(2^w)$ by a factor of~$w$ in each direction to yield a~$w(k+m) \times wk$
matrix which we call a {\em binary distribution matrix (BDM)}.  We multiply
that by a~$wk$ element vector, which is composed of~$w$ bits from each 
data device.  The product is a~$w(k+m)$ element vector composed of~$w$
bits from each data and coding device.  This is depicted in Figure~\ref{fig:gbc}.
It is useful to visualize the matrix as being composed of~$w \times w$ 
sub-matrices.

\begin{figure}[ht]
\begin{center}
\epsfig{figure=General-Bitmatrix-Coding.eps,width=3in} 
\caption{\label{fig:gbc} Describing a coding system with a bit-matrix-vector
product.}
\end{center}
\end{figure}

As with the matrix-vector product in~$GF(2^w)$, each row of the product
corresponds to a row of the BDM, and is computed as the dot product of that 
row and the data bits.  Since all elements are bits, we may perform the 
dot product by taking the XOR of each data bit whose element in the 
matrix's row is one.  In other words, rather than performing the dot
product with additions and multiplications, we perform it only with XORs. 
Moreover, the performance of this dot product is directly related to the
number of ones in the row.  Therefore, it behooves us to find matrices
with few ones.

Decoding with bit-matrices is the same as with matrices over~$GF(2^w)$, except
now each device corresponds to~$w$ rows of the matrix, rather than one.
Also keep in mind that a bit in this description corresponds to a packet
in the implementation.

While the classic construction of bit-matrices starts with a standard
distribution matrix in~$GF(2^w)$, it is possible to construct bit-matrices
that have no relation to Galois Field arithmetic yet still have desired 
coding and decoding properties.  The minimal density RAID-6 codes work in this fashion.

\subsection{Using a schedule rather than a bit-matrix}
\label{sec:sched}

Consider the act of encoding with a bit-matrix.  We give an example
in Figure~\ref{fig:03-01-05}, where~$k=3$, $w=5$, and we are calculating
the contents of one coding device.  The straightforward way to encode
is to calculate the five dot products for each of the five bits of the
coding device, and we can do that by traversing each of the five rows, 
performing XORs where there are ones in the matrix.

\begin{figure}[ht]
\begin{center}
\epsfig{figure=03-01-05.eps,width=2in} 
\caption{\label{fig:03-01-05} An example super-row of a bit-matrix for~$k=3$, 
$w=5$.}
\end{center}
\end{figure}

Since the matrix is sparse, it is more efficient to precompute the coding
operations, rather than traversing the matrix each time one encodes.  The
data structure that we use to represent encoding is a {\em schedule}, which 
is a list of 5-tuples:
\[ < op, s_d, s_b, d_d, d_b >, \]
where~$op$ is an operation code: 0 for copy and 1 for XOR,~$s_d$ is the id
of the source device and~$s_b$ is the bit of the source device.  The last
two elements,~$d_d$ and~$d_b$ are the destination device and bit.  By convention,
we identify devices using integers from zero to~$k+m-1$.  An id~$i < k$ identifies data
device~$D_i$, and an id~$i \ge k$ identifies coding device~$C_{i-k}$.

A schedule for encoding using the bit-matrix in Figure~\ref{fig:03-01-05} is
shown in Figure~\ref{fig:sched}.

\begin{figure}[h]
\begin{center}
\begin{tabular}{l|l}
\hline
$< 0, 0, 0, 3, 0>, <1, 1, 1, 3, 0>, <1, 2, 2, 3, 0>,$ & $c_{0,0} = d_{0,0} \oplus d_{1,1} \oplus d_{2,2} $\\
$< 0, 0, 1, 3, 1>, <1, 1, 2, 3, 1>, <1, 2, 3, 3, 1>,$ & $c_{0,1} = d_{0,1} \oplus d_{1,2} \oplus d_{2,3} $\\
$< 0, 0, 2, 3, 2>, <1, 1, 2, 3, 2>, <1, 1, 3, 3, 2>, <1, 2, 4, 3, 2>,$ & $c_{0,2} = d_{0,2} \oplus d_{1,2} 
                                                                         \oplus d_{1,3} \oplus d_{2,4} $\\
$< 0, 0, 3, 3, 3>, <1, 1, 4, 3, 3>, <1, 2, 0, 3, 3>,$ & $c_{0,3} = d_{0,3} \oplus d_{1,4} \oplus d_{2,0} $\\
$< 0, 0, 4, 3, 4>, <1, 1, 0, 3, 4>, <1, 2, 0, 3, 4>, <1, 2, 1, 3, 4>.$ & $c_{0,4} = d_{0,4} \oplus d_{1,0} 
                                                                         \oplus d_{2,0} \oplus d_{2,1} $\\
\hline
\multicolumn{1}{c}{(a)} &
\multicolumn{1}{c}{(b)}  \\
\end{tabular}
\end{center}
\caption{\label{fig:sched} A schedule of bit-matrix operations for the bit-matrix
in Figure~\ref{fig:03-01-05}. (a) shows the schedule, and (b) shows the dot-product
equations corresponding to each line of the schedule.}
\end{figure}

As noted in~\cite{hdrt:05:mm,p:08:lib}, one can derive schedules for bit-matrix 
encoding and decoding
that make use of common expressions in the dot products, and therefore can perform
the bit-matrix-vector product with fewer XOR operations than simply traversing the
bit-matrix.  This is how RDP encoding works with optimal performance~\cite{ceg:04:rdp}, 
even though there are more than~$kw$ ones in the last~$w$ rows of its BDM.  We term
such scheduling {\em smart} scheduling, and scheduling by simply traversing the matrix
{\em dumb} scheduling.

\section{MDS Codes}

A code is MDS if it can recover the data following the failure of any~$m$
devices.  If a matrix-vector product is used to define the code, then it
is MDS if every combination of~$k$ rows composes an invertible matrix.
If a bit-matrix is used, then we define a {\em super-row} to be a row's
worth of~$w \times w$ submatrices.  The code is MDS if every combination of~$k$
super-rows composes an invertible matrix.  Again, one may generate an MDS
code using standard techniques such as employing a Vandermonde matrix~\cite{pd:05:rs}
or Cauchy matrix~\cite{mor:89:edi,bkk:95:xor}.  However, there are other
constructions that also yield MDS matrices, such as 
EVENODD coding~\cite{bbbm:95:eo}, RDP coding~\cite{ceg:04:rdp}, the 
STAR code~\cite{hx:05:star}, Feng's codes~\cite{fdb:05:rc1,fdb:05:rc2}
and the minimal density RAID-6 codes~\cite{br:99:old,p:08:md8,p:08:lib}.

\section{Part 1 of the Library: Galois Field Arithmetic (galois.h)}

The files {\bf galois.h} and {\bf galois.cpp} contain procedures for Galois Field
arithmetic in~$GF(2^w)$ for~$1 \le w \le 32$. There are functions for performing single
arithmetic operations, XOR-ing a region of bytes, and performing multiplication
of a region of bytes by a constant in~$GF(2^8)$, $GF(2^{16})$ and~$GF(2^{32})$.
All of these procedures are defined in a separate technical report which focuses solely
on Galois Field arithmetic~\cite{p:07:gfl}. The following section lists the Galois functions used by {\bf jerasure}.

\subsection{Galois procedures used in Jerasure - galois.cpp}
\label{sec:galprod}
\begin{itemize}
\item {\bf galois\-\_single\-\_multiply(int a, int b, int w)} and {\bf galois\-\_single\-\_divide(int a, int b, int w)}: These
perform multiplication and division on single elements~{\bf a} and~{\bf b} of~$GF(2^{\bf w})$.

\item  {\bf galois\-\_region\-\_xor(char *r1, char *r2, char *r3, int nbytes)}: This XORs two regions of 
bytes,~{\bf r1} and~{\bf r2} and places the sum in~{\bf r3}.  Note that~{\bf r3} may be equal 
to~{\bf r1} or~{\bf r2} if
we are replacing one of the regions by the sum. {\bf Nbytes} must be a multiple of {\bf 8}.

\item {\bf galois\-\_w08\-\_region\-\_multiply(unsigned char *region, int multby,
int nbytes, unsigned char *r2, int add)}: This multiplies an entire region of
bytes by the constant~{\bf multby} in~$GF(2^8)$.  If~{\bf r2} is {\bf
NULL} then~{\bf region} is overwritten.  Otherwise, if~{\bf add} is
zero, the products are placed in~{\bf r2}.  If~{\bf add} is non-zero,
then the products are XOR'd with the bytes in~{\bf r2}. {\bf Nbytes} must be a multiple of {\bf 8}.

\item {\bf galois\-\_w16\-\_region\-\_multiply()} and 
{\bf galois\-\_w32\-\_region\-\_multiply()} are identical to {\bf galois\-\_w08\-\_region\-\_multiply()},
except they are in~$GF(2^{16})$ and~$GF(2^{32})$ respectively. {\bf Nbytes} must still be a multiple of {\bf 8}.

\item {\bf galois\_\-w08\_\-region\_\-multby\_\-2(char *region, int nbytes)}:
This performs the fast multiplication by two in~$GF(2^8)$ using Anvin's optimization~\cite{a:07:mr6}. {\bf Nbytes} must be a multiple of {\bf 8}.

\item {\bf galois\_\-w16\_\-region\_\-multby\_\-2()} and {\bf galois\_\-w32\_\-region\_\-multby\_\-2()} are identical to {\bf galois\_\-w08\_\-region\_\-multby\_\-2()}, except they are in~$GF(2^{16})$ and~$GF(2^{32})$ respectively. {\bf Nbytes} must still be a multiple of {\bf 8}.
\end{itemize}

\subsection{Example programs}
    \begin{itemize}

        \item {\bf galois\_01.cpp}:
            This simply demonstrates doing fast multiplication 
            by two in~$GF(2^w)$ for~$w \in \{8,16,32\}$.  It has one parameter:~$w$.
            {\footnotesize \begin{verbatim}
            UNIX> galois_01 16
            Short  0: 58899 *2 = 56365
            Short  1: 54100 *2 = 46755
            Short  2: 64788 *2 = 59939
            Short  3: 52269 *2 = 34897
            Short  4: 47389 *2 = 25137
            Short  5: 42657 *2 = 23881
            Short  6: 49248 *2 = 37067
            Short  7:  4812 *2 =  9624
            UNIX> 
            \end{verbatim}}
            This demonstrates usage of 
            {\bf galois\_\-w08\_\-region\_\-multby\_\-2()},
            {\bf galois\_\-w16\_\-region\_\-multby\_\-2()} and
            {\bf galois\_\-w32\_\-region\_\-multby\_\-2()}.
    \end{itemize}

\section{Part 2 of the Library: Kernel Classes (jerasure.h)}
\label{sec:kernel}

{\bf Jerasure.h} contains prototypes of the functions necessary for coding. This header file also specifies the different classes used in the encoding process. Function declarations are split into object files based on the class with which they are associated. We will discuss the contents of this library on a class basis. We give example programs that make use of them in Section~\ref{sec:keruse} below. We will decribe the procedures that compose {\bf jerasure.h} by the .cpp files in which they are found.

\subsection{Encoding and decoding data - jer\_slices.cpp}
The JER\_Slices class links the user data to a generator and manages the drive states. JER\_Slices also contains the methods related to encoding and decoding data. The class contains the following variables:
\begin{itemize}
\item{\bf int K}: The number of data devices.
\item{\bf int N}: The total number of devices. This is the sum of the number of data devices ({\bf K}) and the number of coding devices (M). The number of coding devices is not stored, but it is calculated as {\bf N}-{\bf K}.
\item{\bf JER\_Gen\_T *G}: The generator used to encode and decode the data.
\item{\bf int PacketSize}: The packet size as defined in section~\ref{sec:intro}. This must be a multiple of {\bf 8}.
\item{\bf int PacketsPerSlice}: The number of packets in a single device. This must be a multiple of {\bf G}$\rightarrow${\bf WPD}.
\item{\bf vector $\langle$unsigned char *$\rangle$ Ptrs}: This is an array of pointers with one element per device. Each pointer should point to {\bf PacketSize} * {\bf PacketsPerSlice} bytes of data. {\bf Ptrs} is initialized in the {\bf JER\_Slices} constructors. For constructors with a {\bf ptrs} argument, {\bf Ptrs} is set to a copy of {\bf ptrs}. Otherwise, {\bf Ptrs} is resized to size {\bf N}.
\item{\bf int DataOnly}: This variable is only used for vertical codes. It is set by the user in one of the {\bf JER\_Slices} constructors. When {\bf DataOnly} $\neq$ 0, it is assumed that the user-provided {\bf Ptrs} do not contain encoded data. Therefore, all {\bf N} drives are set to the “down” state. If {\bf DataOnly} = 0, it is assumed that {\bf Ptrs} contains encoded data, and all {\bf N} drives are set to the “up” state.
\item{\bf vector $\langle$int$\rangle$ States}: This vector describes whether a particular drive is “up”, “down”, or “unusable”. The state of the ith drive is stored in {\bf States}[i]. Valid values for elements of {\bf States} include 0, 1, or 2. These values correspond respectively to a drive being “up”, “down”, or “unusable”. The {\bf JER\_Slices} constructors resize {\bf States} to size {\bf N}.
\item{\bf int NumberOfCores}: The number of cores that the user's machine has. This variable is set to a default value of 1 in the {\bf JER\_Slices} constructors. However, users may update the value at any time. Some procedures, such as encoding or decoding with a bitmatrix, will attempt to create a thread for each core. Each thread will work independently on its task in order to incease performance.
\item{\bf string MultiThreadMethod}: This variable holds the name of the technique to be used when performing multi-threaded dot products on bit-matrices. The technique names describe the amount of data that each thread will work with. Valid values include {\em disks}, {\em packet\_rows}, {\em packet\_cols}, or {\em packets}. An undefined value will default to the technique that handles the largest chunks of data, while allowing a separate thread for each core.
\item{\bf int XORs}: The total number of bytes that have been xorred. This is incremented after methods call {\bf galois\_region\_xor()}.
\item{\bf int GF\_Mults}: The total number of bytes that have been multiplied by a constant in $GF(2^w)$. This is incremented when methods call {\bf galois\_w08\_region multiply()}, {\bf galois\_w16\_region\_multiply()}, or {\bf galois\_w32\_region\_multiply()}.
\item{\bf int Memcpys}: The number of bytes that have been copied using memcpy().
\end{itemize}

The member functions of JER\_Slices handle the manipulation of the data. The following functions are members of the class.
\begin{itemize}
\item{\bf JER\_Slices(int n, int k, int ps, int pps, JER\_Gen\_T *g, vector $\langle$unsigned char *$\rangle$ ptrs, int data\_only)}: This constructor is used when data is setup in a format suitable for vertical coding. The {\bf ptrs} argument should contain {\bf N} pointers to memory allocated for the data. If {\bf data\_only} = 0, it is assumed that the data pointed to by {\bf ptrs} is already properly encoded. All drives are given a state of {\em up}. If {\bf data\_only} is non-zero, it is assumed that the data is not encoded. All drives are given a state of {\em down}. {\bf Encode()} is not called in this constructor. {\bf All constructors initialize XORs, GF\_Mults, and Memcpys to 0, NumberOfCores to 1, and MultiThreadMethod to "".}
\item{\bf JER\_Slices(int n, int k, int ps, int pps, JER\_Gen\_T *g, vector $\langle$unsigned char *$\rangle$ ptrs)}: This constructor copies the {\bf ptrs} argument to {\bf Ptrs}. The first {\bf K} drive states are {\em up}, and the coding drives are set to {\em down}. {\bf Encode()} is then called, and the coding drives are set to {\em up} if encoding occurs successfully.
\item{\bf JER\_Slices(int n, int k, int ps, int pps, JER\_Gen\_T *g)}: This constructor resizes {\bf Ptrs} to contain {\bf N} elements. The first {\bf K} drives are set to {\em up}, and the coding drives are set to {\em down}. {\bf Encode()} is not called.
\item{\bf void Add\_Partial\_Failure(int drive, int start, int size)}: Creates a new {\bf JER\_Region} object, sets its values, and appends it to {\bf Pfs}.
\item{\bf void Add\_Partial\_Failure(JER\_Region \&r)}: Appends the {\bf JER\_Region} argument to {\bf Pfs}.
\item{\bf void Add\_Drive\_Failure(int drive)}: Assigns a state of {\em down} to the device with an id of {\bf drive} ({\bf States}[{\bf drive}] = 1).
\item{\bf void Remove\_Drive(int drive)}: Deletes the device with an id of {\bf drive}. The drive's entries in {\bf Ptrs} and {\bf States} are erased. The generator matrix is modified to work with {\bf N}-1 devices.
\item{\bf void Remove\_Drive\_And\_Re\_Encode(int drive)}: This simply calls {\bf Remove\_Drive(drive)} then {\bf Encode()}.
\item{\bf int Encode()}: If the generator matrix is a bitmatrix ({\bf G}$\rightarrow${\bf M}$\rightarrow${\bf W} $= 1$), the procedure first tries to find an encoding schedule. If the schedule is found, it is used to encode. Otherwise, encoding is performed by calling {\bf Dotprod()}.For generator matrices with {\bf W} $\neq 1$, this encodes with a matrix in $GF(2^w)$ as described in Section 3 above. If ({\bf N}-{\bf K}) = 2, and the generator's {\bf rs\_r6} property is {\em true}, this encodes using Anvin's optimization. Encoding via Anvin's method does not require the generator to have a matrix, because the coding matrix is implicit. Sets all coding drive states to {\em up} and returns 0 on success; sets all drive states to {\em down} and returns -1 on failure.
\item{\bf int Decode()}: If the generator matrix is a bitmatrix ({\bf G}$\rightarrow${\bf M}$\rightarrow${\bf W} $= 1$) and ({\bf N}-{\bf K}) = 2, the procedure first tries to find the schedule matching the current drive states. If the schedule is found, it is used to decode. Otherwise, decoding is performed by calling {\bf Dotprod()}. For generator matrices with {\bf W} $\neq 1$, this decodes using a matrix in $GF(2^w)$, {\bf W} $\in \{8, 16, 32\}$. This works by creating a decoding matrix and performing the matrix/vector product, then re-encoding any erased coding devices. When it is done, the decoding matrix is discarded. If you want access to the decoding matrix, you should use the {\bf Make\_Decoding\_Matrix()} method listed below. Sets all drive states to {\em up} and returns 0 on success; leaves drive states unaltered and returns -1 on failure.
\item{\bf int Decode\_Schedule\_Lazy(int smart)}: This decodes the data using a schedule. It first searches {\bf G}$\rightarrow${\bf Schedules} for a schedule matching the current drive states. If a suitable schedule is not found, it is created. If {\bf smart} = 1, the newly created schedule's type is CSHR. The new schedule is deleted once decoding is complete, and it is not inserted into {\bf G}$\rightarrow${\bf Schedules}. The function will fail if the generator matrix is not a bitmatrix (if {\bf G}$\rightarrow${\bf W} $\neq 1$). Sets all drive states to {\em up} and returns 0 on success; leaves drive states unaltered and returns -1 on failure.
\item{\bf int Dotprod(JER\_Matrix *jm, vector $\langle$int$\rangle$ \& jm\_super\_rows, vector $\langle$int$\rangle$ \& dest\_disk\_ids, int *dm\_ids)}: For each element in {\bf jm\_super\_row\_ids}, this multiplies the specified super-row of matrix {\bf jm} by the devices listed in {\bf dm\_ids}. {\bf Dm\_ids} should either be NULL, or contain {\bf K} integers. If {\bf dm\_ids} is NULL, the first {\bf K} devices are used. The result of multiplying {\bf jm}'s super-row, {\bf jm\_super\_rows}[i], by {\bf K} devices is placed in the device with an id of {\bf dest\_disk\_ids}[i]. The number of elements in {\bf jm\_super\_rows} and {\bf dest\_dist\_ids} must match. When a one is encountered in the matrix {\bf jm}, the proper XOR/copy operation is performed. Otherwise, the operation is multiplication by the matrix element in $GF(2^w)$ and an XOR into the destination. If {\bf NumberOfCores} is $\le$ 1, this procedure is not multi-threaded, and each destination disk is processed separately. If {\bf NumberOfCores} $>$ 1, this will create multiple threads, and split the work among them. The exact number of threads and method for dividing the work depends upon the value of {\bf MultiThreadMethod}. Returns 0 on success, -1 on failure.
\item{\bf JER\_Matrix * Make\_Decoding\_Matrix(int *dm\_ids)}: This does not decode, but instead creates the decoding matrix. Note that {\bf dm\_ids} should be allocated and passed to this procedure, which will fill them in. {\bf Dm\_ids} should have {\bf K} integers. Returns NULL on failure.
\item{\bf void Do\_Parity(unsigned char * parity\_ptr)}: This calculates the parity of the first {\bf K} devices in {\bf Ptrs}. It puts the result into the {\bf PacketSize} * {\bf PacketsPerSlice} bytes pointed to by {\bf parity\_ptr}. The size of {\bf parity\_ptr} must be a multiple of 8.
\end{itemize}
\subsection{Generator matrices and scheduling - jer\_gen\_t.cpp}
The JER\_Gen\_T class handles the generator matrix and scheduling. Procedures in {\bf reed\_sol.cpp} and {\bf bitmatrices.cpp} are used to create generators for various coding schemes. The variables that are members of this class are as follows:
\begin{itemize}
\item{\bf int K}: Identical to {\bf K} in {\bf JER\_Slices}, number of data drives.
\item{\bf int N}: Identical to {\bf N} in {\bf JER\_Slices}, total number of drives.
\item{\bf JER\_Matrix * M}: The coding matrix. For systematic codes, the matrix is of size ({\bf K}*{\bf WPD}) X (({\bf N}-{\bf K})*{\bf WPD}). Otherwise, the dimensions are ({\bf K}*{\bf WPD})X({\bf N}*{\bf WPD}).
\item{\bf int WPD}: Words per drive. Indicates how many rows/columns of {\bf M} are to be grouped together and considered as a super-row/column. Generally used when dealing with bitmatrices.
\item{\bf bool Systematic}: Whether or not the generator represents a systematic code. This is set for the user in the generator creation functions.
\item{\bf bool PDrive}: Parity drive. Whether or not the first row of the coding matrix is all ones. When the coding matrix is a bitmatrix, this property should be true when the first {\bf WPD} rows compose {\bf K} identity matrices. This is set for the user in the generator creation functions. When ({\bf N}-{\bf K}) $>$ 1 and the first row of the coding matrix is composed of all ones, then there are times when we can improve the performance of decoding by not following the methodology described in Section 3. This is true when coding device zero is one of the survivors, and more than one data device has been erased. In this case, it is better to decode all but one of the data devices as described in Section 3, but decode the last data device using the other data devices and coding device zero. For this reason, {\bf PDrive} should be true if the first row of the coding matrix is all ones.
\item{\bf bool rs\_r6}: Whether or not the generator matrix is a Reed-Solomon RAID 6 coding matrix. This property defaults to false, but it is set to true in {\bf RS\_R6\_Generator()} (located in reed\_sol.cpp). If {\bf rs\_r6} is true, {\bf Encode()} will use Anvin's optimization.
\item{\bf map $\langle$string, JER\_Schedule *$\rangle$ Schedules}: Cache containing encode and decode schedules. The map is keyed on strings of {\bf N} 1's and 0's. Each character represents the state of a drive (0 = {\em up} and 1 = {\em down}).
\end{itemize}
The following methods are members of the JER\_Gen\_T class.
\begin{itemize}
\item{\bf ~JER\_Gen\_T()}: The class deconstructor simply calls the {\bf Delete\_Schedules()} method explained below.
\item{\bf int Am\_I\_MDS()}: Determines if the coding matrix, {\bf M}, represents a maximum distance separable (MDS) code. The generator is MDS if {\bf M} is invertible when any combinations of ({\bf N}-{\bf K}) rows are removed. Returns 1 if the matrix is MDS, 0 if it is not MDS, and -1 on failure.
\item{\bf int Create\_Encode\_Schedule(int smart)}: This method creates a schedule for encoding. If {\bf smart} = 1, the newly created schedule's type is CSHR. The new schedule is inserted into the {\bf Schedules} map. If the map already contains an encode schedule, the old schedule will be deleted. If {\bf M} is not a bitmatrix ({\bf M}$\rightarrow${\bf W}$\neq 1$), nothing is done and {\bf Create\_Encode\_Schedule()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf int Create\_R6\_Schedules(int smart)}: First, this method deletes all schedules in {\bf Schedules}. It then generates the encoding schedule, and schedules for every combination of single and double-disk erasure decoding. If {\bf smart} = 1, it creates CSHR schedules. If {\bf M} is not a bitmatrix ({\bf M}$\rightarrow${\bf W}$\neq 1$) or ({\bf N}-{\bf K})$\neq 2$, nothing is done and {\bf Create\_R6\_Schedules()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf void Delete\_Schedules()}: This method calls delete on all of the schedules in {\bf Schedules}. The {\bf Schedules} map is then emptied. This is called for the user in the {\bf JER\_\-Gen\_\-T} deconstructor.
\item{\bf JER\_Schedule * Create\_Single\_Decode\_Schedule(vector $\langle$int$\rangle$ \& erased, int smart)}: Returns a schedule for decoding given a set of failed drives. If {\bf M} is not a bitmatrix ({\bf M}$\rightarrow${\bf W}$\neq 1$), nothing is done and returns failed. Returns NULL on failure.
\item{\bf JER\_Gen\_T *Genmatrix\_To\_Genbitmatrix()}: This method is called on a generator whose coding matrix has {\bf W} $\neq$ 1. It returns a new generator whose coding matrix has {\bf W} = 1. The newly returned generator's properties, including {\bf WPD}, are updated accordingly. Returns NULL on failure.
\item{\bf JER\_Gen\_T *Genbitmatrix\_To\_Genmatrix()}: This method is called on a generator whose coding matrix has {\bf W} = 1. It returns a new generator whose coding matrix has {\bf W} = {\bf WPD}. The newly returned generator's properties, including {\bf WPD}, are updated accordingly. Returns NULL on failure.
\item{\bf int Genmatrix\_To\_Genbitmatrix(JER\_Gen\_T \&bgen)}: This method is called on a matrix generator, and passed a {\bf JER\_Gen\_T} object ({\bf bgen}). {\bf Bgen} is converted to a bitmatrix representation of the current generator. Returns 0 on success, -1 on failure.
\item{\bf int Genbitmatrix\_To\_Genmatrix(JER\_Gen\_T \&gen)}: This method is called on a bitmatrix generator. The argument, {\bf gen}, is converted to a matrix representation of the current generator. Returns 0 on success, -1 on failure.
\end{itemize}
\subsection{Matrices and their basic operations - jer\_matrix.cpp}
The JER\_Matrix class handles all objects and operations associated with matrices and matrix manipulation. The JER\_Matrix class contains the following variables:
\begin{itemize}
\item{\bf int R}: The number of rows the matrix contains.
\item{\bf int C}: The number of columns the matrix contains.
\item{\bf int W}: All elements of the matrix will be elements of GF($2^W$) and the galois field will be used in all operations concerning this matrix.
\item{\bf vector$\langle$uint64\_t$\rangle$ Elts}: The container in which the elements reside. The packing of the vector is dependent on {\bf W} and not generally aligned with the elements of the vector.
\end{itemize}
There are also functions associated with the JER\_Matrix class. The following methods belong to the class. Any mention of the matrix refers to the JER\_Matrix object through which the method is being called.
\begin{itemize}
\item{\bf JER\_Matrix()}: Constructs a matrix object, but does not initialize any variables.
\item{\bf JER\_Matrix( int r, int c, int w )}: Constructs a matrix object, initializes {\bf R}, {\bf C}, and {\bf W} to the specified values, and resizes {\bf Elts} appropriately. {\bf Elts} contains all zeros after resizing.
\item{\bf int Create\_Empty( int r, int c, int w )}: Sets {\bf R}, {\bf C}, and {\bf W} accordingly. Clears the values in {\bf Elts} and resizes the vector to be of appropriate size. {\bf Elts} contains all zeros after resizing. Return 0 on success, -1 on failure.
\item{\bf int Create\_Identity( int r, int c, int w )}: Sets {\bf R}, {\bf C}, and {\bf W} accordingly. Resizes {\bf Elts} appropriately and sets the values on the diagonal to ones in order to create an identity matrix. If {\bf r}$\neq${\bf c}, nothing is done and {\bf Create\_Identity()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf void Set( int r, int c, uint64\_t val )}: Sets the {\bf r},{\bf c} element of the matrix to {\bf val}. Behavior not specified if {\bf val}$ \notin GF(2^W)$.
\item{\bf uint64\_t Get( int r, int c )}: Returns the value of the {\bf r},{\bf c} element.
\item{\bf void Print()}: Prints the matrix to stdout. 
\item{\bf void Print( int WPD )}: Prints the matrix to stdout. Adds extra padding every {\bf WPD} rows and columns to help distinguish super rows and super columns in the case of a bitmatrix.
\item{\bf string String()}: Returns a string of the contents of the matrix.
\item{\bf string String( int WPD )}: Returns a string of the contents of the matrix. Adds extra padding every {\bf WPD} rows and columns to help distinguish super rows and super columns in the case of a bitmatrix.
\item{\bf int Copy( JER\_Matrix* m )}: Sets {\bf R}, {\bf C}, and {\bf W} to that of {\bf m}. Copies the elements of {\bf m} into the matrix, resizing {\bf Elts} in the process. Returns 0 on success, -1 on failure.
\item{\bf int Add( JER\_Matrix *m )}: Xors each element of the matrix with its corresponding element in {\bf m}, stores the result in the matrix. If {\bf R}, {\bf C}, {\bf W} $\neq$ {\bf m}$\rightarrow$ {\bf R}, {\bf m}$\rightarrow$ {\bf C}, {\bf m}$\rightarrow$ {\bf W}, nothing is done and {\bf Add()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf int Append\_Row( JER\_Matrix *m, int r )}: Appends the r$^{th}$ row of m to the matrix. If {\bf C}, {\bf W} $\neq$ {\bf m}$\rightarrow$ {\bf C}, {\bf m}$\rightarrow$ {\bf W}, nothing is done and {\bf Append\_Row()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf int Append\_Col( JER\_Matrix *m, int c )}: Appends the {\bf c}$^{th}$ column of {\bf m} to the matrix. If {\bf R}, {\bf W} $\neq$ {\bf m}$\rightarrow$ {\bf R}, {\bf m}$\rightarrow$ {\bf W}, nothing is done and {\bf Append\_Col()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf int Delete\_Row( int r )}: Deletes the {\bf r}$^{th}$ row of the matrix. Resizes {\bf Elts} accordingly. Returns 0 on success, -1 on failure.
\item{\bf int Delete\_Col( int c )}: Deletes the {\bf c}$^{th}$ column of the matrix. Resizes {\bf Elts} accordingly. Returns 0 on success, -1 on failure.
\item{\bf int Delete\_Rows( int starting\_r, int nr )}: Deletes {\bf nr} rows of the matrix, beginning with {\bf starting\_r}. Resizes {\bf Elts} accordingly. Returns 0 on success -1 on failure.
\item{\bf int Delete\_Cols( int starting\_c, int nc )}: Deletes {\bf nc} columns of the matrix, beginning with {\bf starting\_c}. Resizes {\bf Elts} accordingly. Returns 0 on success -1 on failure.
\item{\bf int Copy\_Panel( JER\_Matrix *m, int dest\_r, int dest\_c )}: Copies {\bf m} into the matrix placing {\bf m}[0][0] at matrix[{\bf dest\_r}][{\bf dest\_c}]. If {\bf R} $<$ {\bf m}$\rightarrow${\bf R} + {\bf dest\_r} or {\bf C} $<$ {\bf m}$\rightarrow${\bf C} + {\bf dest\_c} or {\bf W} $\neq$ {\bf m}$\rightarrow${\bf W}, nothing is done and {\bf Copy\_Panel()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf int Copy\_Panel( JER\_Matrix *m, int src\_r, int src\_c,int dest\_r, int dest\_c, int nr, int nc )}: Copies an {\bf nr} by {\bf nc} portion of {\bf m} into the matrix placing {\bf m}[{\bf src\_r}][{\bf src\_c}] at matrix[{\bf dest\_r}][{\bf dest\_c}]. If {\bf R} $<$ {\bf nr} + {\bf dest\_r} or {\bf C} $<$ {\bf nc} + {\bf dest\_c} or {\bf m}$\rightarrow${\bf R} $<$ {\bf nr} + {\bf src\_r} or {\bf m}$\rightarrow${\bf C} $<$ {\bf nc} + {\bf src\_c} or {\bf W} $\neq$ {\bf m}$\rightarrow${\bf W}, nothing is done and {\bf Copy\_Panel()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf int Add\_Panel( JER\_Matrix *m, int dest\_r, int dest\_c )}: Adds {\bf m} into the matrix xorring {\bf m}[0][0] with matrix[{\bf dest\_r}][{\bf dest\_c}]. If {\bf R} $<$ {\bf m}$\rightarrow${\bf R} + {\bf dest\_r} or {\bf C} $<$ {\bf m}$\rightarrow${\bf C} + {\bf dest\_c} or {\bf W} $\neq$ {\bf m}$\rightarrow${\bf W}, nothing is done and {\bf Add\_Panel()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf int Add\_Panel( JER\_Matrix *m, int src\_r, int src\_c,int dest\_r, int dest\_c, int nr, int nc )}: Adds an {\bf nr} by {\bf nc} portion of {\bf m} into the matrix xorring {\bf m}[{\bf src\_r}][{\bf src\_c}] with matrix[{\bf dest\_r}][{\bf dest\_c}]. If {\bf R} $<$ {\bf nr} + {\bf dest\_r} or {\bf C} $<$ {\bf nc} + {\bf dest\_c} or {\bf m}$\rightarrow${\bf R} $<$ {\bf nr} + {\bf src\_r} or {\bf m}$\rightarrow${\bf C} $<$ {\bf nc} + {\bf src\_c} or {\bf W} $\neq$ {\bf m}$\rightarrow${\bf W}, nothing is done and {\bf Add\_Panel()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf void Horizontal\_Rotate( int cols )}: Shifts each column of the matrix left by {\bf cols}, wrapping around those columns who would go out of range. If {\bf cols} is negative, the columns are shifted right. 
\item{\bf void Vertical\_Rotate( int rows )}: Shifts each row of the matrix up by {\bf rows}, wrapping around those rows who would go out of range. If {\bf rows} is negative, the rows are shifted down.
\item{\bf void Swap\_Rows( int r1, int r2 )}: Swaps rows {\bf r1} and {\bf r2} of the matrix.
\item{\bf void Swap\_Cols( int c1, int c2 )}: Swaps columns {\bf c1} and {\bf c2} of the matrix.
\item{\bf void Row\_PlusEquals( int r1, int r2 )}: Stores in row {\bf r1} the xor of rows {\bf r1} and {\bf r2}.
\item{\bf void Col\_PlusEquals( int c1, int c2 )}: Stores in column {\bf c1} the xor of columns {\bf c1} and {\bf c2}.
\item{\bf void Row\_PlusEquals\_Prod( int r1, int r2, int prod )}: Stores in row {\bf r1} the xor of rows {\bf r1} and ( {\bf r2} * {\bf prod} ) in $GF(2^W)$.
\item{\bf void Col\_PlusEquals\_Prod( int c1, int c2, int prod )}: Stores in column {\bf c1} the xor of column {\bf c1} and ( {\bf c2} * {\bf prod} ) in $GF(2^W)$.
\item{\bf void Row\_TimesEquals( int r1, int prod )}: Multiplies row {\bf r1} of the matrix by {\bf prod} in $GF(2^W)$.
\item{\bf void Col\_TimesEquals( int c1, int prod )}: Multiplies column {\bf c1} of the matrix by {\bf prod} in $GF(2^W)$.
\item{\bf JER\_Schedule *To\_Schedule\_CSHR( int WPD )}: Creates and returns a schedule based off of the matrix. {\bf WPD} indicates how many rows/columns form a super-row/column. If {\bf W} $\neq 1$ or {\bf C},{\bf R} $= 0$, nothing is done and {\bf To\_Schedule\_CSHR()} returns failed. Returns NULL on failure. Uses Code Specific Hybrid Reconstruction to generate the schedule.
\item{\bf JER\_Schedule *To\_Schedule\_Dumb( int WPD )}: Creates and returns a schedule based off of the matrix. {\bf WPD} indicates how many rows/columns form a super-row/column. If {\bf W} $\neq 1$ or {\bf C},{\bf R} $= 0$, nothing is done and {\bf To\_Schedule\_Dumb()} returns failed. Returns NULL on failure.
\item{\bf JER\_Matrix *Matrix\_To\_Bitmatrix()}: Creates and returns a matrix that is the bitmatrix representation of the original matrix. Changes {\bf W} to one. Returns NULL on failure. 
\item{\bf JER\_Matrix *Bitmatrix\_To\_Matrix( int WPD )}: Creates and returns a matrix that is the matrix representation of the original bitmatrix. {\bf WPD} indicates the galois field into which to convert the bitmatrix. After conversion {\bf W} = {\bf WPD}. If {\bf W} $\neq 1$, nothing is done and {\bf Bitmatrix\_To\_Matrix()} returns failed. Returns NULL on failure.
\item{\bf int Matrix\_To\_Bitmatrix( JER\_Matrix \&jbm )}: Modifies {\bf jbm} to be the bitmatrix representation of the original matrix. Changes {\bf W} to one. Returns 0 on success, -1 on failure. 
\item{\bf int Bitmatrix\_To\_Matrix( JER\_Matrix \&jm, int WPD )}: Modifies {\bf jm} to be the matrix representation of the original bitmatrix. {\bf WPD} indicates the galois field into which to convert the bitmatrix. After conversion {\bf W} = {\bf WPD}. If $W \neq 1$, nothing is done and {\bf Bitmatrix\_To\_Matrix()} returns failed. Returns 0 on success, -1 on failure.
\end{itemize}
These next methods do not belong to the JER\_Matrix class, but are stongly associated with the class and their specifications can be found in jer\_matrix.cpp.
\begin{itemize}
\item{\bf JER\_Matrix *Sum( JER\_Matrix *m1, JER\_Matrix *m2 )}: Creates and returns a matrix that is the xor of the two provided matrices. If {\bf m1}$\rightarrow${\bf R}, {\bf m1}$\rightarrow${\bf C}, {\bf m1}$\rightarrow${\bf W} $\neq$ {\bf m2}$\rightarrow${\bf R}, {\bf m2}$\rightarrow${\bf C}, {\bf m2}$\rightarrow${\bf W}, nothing is done and {\bf Sum()} returns failed. Returns NULL on failure.
\item{\bf int Sum( JER\_Matrix *m1, JER\_Matrix *m2, JER\_Matrix *sum )}: Modifies {\bf sum} to be the xor of the two provided matrices. If {\bf m1}$\rightarrow${\bf R}, {\bf m1}$\rightarrow${\bf C}, {\bf m1}$\rightarrow${\bf W} $\neq$ {\bf m2}$\rightarrow${\bf R}, {\bf m2}$\rightarrow${\bf C}, {\bf m2}$\rightarrow${\bf W}, nothing is done and {\bf Sum()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf int Sum( JER\_Matrix \&m1, JER\_Matrix \&m2, JER\_Matrix \&sum )}: Modifies {\bf sum} to be the xor of the two provided matrices. If {\bf m1}$\rightarrow${\bf R}, {\bf m1}$\rightarrow${\bf C}, {\bf m1}$\rightarrow${\bf W} $\neq$ {\bf m2}$\rightarrow${\bf R}, {\bf m2}$\rightarrow${\bf C}, {\bf m2}$\rightarrow${\bf W}, nothing is done and {\bf Sum()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf JER\_Matrix *Prod( JER\_Matrix *m1, JER\_Matrix *m2 )}: Creates and returns a matrix that is the product of the two provided matrices in $GF(2^W)$. If {\bf m1}$\rightarrow${\bf R}, {\bf m1}$\rightarrow${\bf C}, {\bf m1}$\rightarrow${\bf W} $\neq$ {\bf m2}$\rightarrow${\bf R}, {\bf m2}$\rightarrow${\bf C}, {\bf m2}$\rightarrow${\bf W}, nothing is done and {\bf Prod()} returns failed. Returns NULL on failure.
\item{\bf int Prod( JER\_Matrix *m1, JER\_Matrix *m2, JER\_Matrix *prod )}: Modifies {\bf prod} to be the product of the two provided matrices in $GF(2^W)$. If {\bf m1}$\rightarrow${\bf R}, {\bf m1}$\rightarrow${\bf C}, {\bf m1}$\rightarrow${\bf W} $\neq$ {\bf m2}$\rightarrow${\bf R}, {\bf m2}$\rightarrow${\bf C}, {\bf m2}$\rightarrow${\bf W}, nothing is done and {\bf Prod()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf int Prod( JER\_Matrix \&m1, JER\_Matrix \&m2, JER\_Matrix \&prod )}: Modifies {\bf prod} to be the product of the two provided matrices in $GF(2^W)$. If {\bf m1}$\rightarrow${\bf R}, {\bf m1}$\rightarrow${\bf C}, {\bf m1}$\rightarrow${\bf W} $\neq$ {\bf m2}$\rightarrow${\bf R}, {\bf m2}$\rightarrow${\bf C}, {\bf m2}$\rightarrow${\bf W}, nothing is done and {\bf Prod()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf JER\_Matrix *Inverse( JER\_Matrix *m1 )}: Creates and returns a matrix that is the inverse of {\bf m1}. If {\bf m1}$\rightarrow${\bf R} $\neq$ {\bf m2}$\rightarrow${\bf C}, nothing is done and {\bf Inverse()} returns failed. Returns NULL on failure.
\item{\bf int Inverse( JER\_Matrix *m1, JER\_Matrix *inv )}: Modifies {\bf inv} to be the inverse of {\bf m1}. If {\bf m1}$\rightarrow${\bf R} $\neq$ {\bf m2}$\rightarrow${\bf C}, nothing is done and {\bf Inverse()} returns failed. Returns 0 on success, -1 on failure.
\item{\bf int Inverse( JER\_Matrix \&m1, JER\_Matrix \&inv )}: Modifies {\bf inv} to be the inverse of {\bf m1}. If {\bf m1}$\rightarrow${\bf R} $\neq$ {\bf m2}$\rightarrow${\bf C}, nothing is done and {\bf Inverse()} returns failed. Returns 0 on success, -1 on failure.
\end{itemize}

\subsection{Example programs}
\label{sec:keruse}

The following programs reside in the {\bf Examples} directory. These demonstrate the usage of the classes contained in {\bf jerasure.h}.  They are as follows:

\begin{itemize}
\item {\bf jerasure\_01.cpp}: This takes three parameters: $r$, $c$ and $w$.  It creates
an~$r \times c$ matrix in~$GF(2^w)$, where the element in row~$i$, column~$j$ is equal
to~$2^{ci+j}$ in~$GF(2^w)$.  Rows and columns are zero-indexed.  Example:
{\footnotesize \begin{verbatim}
UNIX> jerasure_01 3 15 8
  1   2   4   8  16  32  64 128  29  58 116 232 205 135  19
 38  76 152  45  90 180 117 234 201 143   3   6  12  24  48
 96 192 157  39  78 156  37  74 148  53 106 212 181 119 238
UNIX> 
\end{verbatim}}
This demonstrates usage of
{\bf galois\_\-single\_\-multiply()},
{\bf JER\_\-Matrix::Set()}, and
{\bf JER\_\-Matrix::Print()}.

\item {\bf jerasure\_02.cpp}: This takes three parameters: $r$, $c$ and $w$.  It creates
the same matrix as in {\bf jerasure\_01}, and then converts it to a~$rw \times cw$
bit-matrix and prints it out.
Example:
{\footnotesize \begin{verbatim}
UNIX> jerasure_02 3 10 4
1000 0001 0010 0100 1001 0011 0110 1101 1010 0101
0100 1001 0011 0110 1101 1010 0101 1011 0111 1111
0010 0100 1001 0011 0110 1101 1010 0101 1011 0111
0001 0010 0100 1001 0011 0110 1101 1010 0101 1011

1011 0111 1111 1110 1100 1000 0001 0010 0100 1001
1110 1100 1000 0001 0010 0100 1001 0011 0110 1101
1111 1110 1100 1000 0001 0010 0100 1001 0011 0110
0111 1111 1110 1100 1000 0001 0010 0100 1001 0011

0011 0110 1101 1010 0101 1011 0111 1111 1110 1100
1010 0101 1011 0111 1111 1110 1100 1000 0001 0010
1101 1010 0101 1011 0111 1111 1110 1100 1000 0001
0110 1101 1010 0101 1011 0111 1111 1110 1100 1000
UNIX> 
\end{verbatim}}
This demonstrates usage of
{\bf galois\_single\_multiply()},
{\bf JER\_\-Matrix::Set()},
{\bf JER\_\-Matrix::Matrix\_\-To\_\-Bitmatrix()}, and
{\bf JER\_\-Matrix::Print()}.

\item {\bf jerasure\_03.cpp}: This takes three parameters: $k$ and $w$.  It creates
a~$k \times k$ Cauchy matrix in~$GF(2^w)$, and tests invertibility.  

The parameter~$k$ must be less than~$2^w$.
The element in row~$i$, column~$j$ is set to:
\[ \frac{1}{i \oplus (2^w-j-1)} \]
where division is in~$GF(2^w)$, $\oplus$ is XOR and subtraction is regular integer
subtraction.  When~$k > 2^{w-1}$, there will be~$i$ and~$j$ such that 
$i \oplus (2^w-j-1) = 0$.  When that happens, we set that matrix element to zero.

After creating the matrix and printing it, we test whether it is
invertible.  If~$k \le 2^{w-1}$, then it will be invertible.  Otherwise
it will not.  Then, if it is invertible, it prints the inverse, then 
multplies the inverse by the original matrix and prints the product which 
is the identity matrix.
Examples:
{\footnotesize \begin{verbatim}
UNIX> jerasure_03 4 3
The Cauchy Matrix:
4 3 2 7
3 4 7 2
2 7 4 3
7 2 3 4

Invertible: Yes

Inverse:
1 2 5 3
2 1 3 5
5 3 1 2
3 5 2 1

Inverse times matrix (should be identity):
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

UNIX> 

UNIX> jerasure_03 5 3
The Cauchy Matrix:
4 3 2 7 6
3 4 7 2 5
2 7 4 3 1
7 2 3 4 0
6 5 1 0 4

Invertible: No

UNIX> 
\end{verbatim}}
This demonstrates usage of 
{\bf galois\_single\_divide()},
{\bf JER\_\-Matrix::Set()},
{\bf JER\_\-Matrix::Print()},
{\bf Inverse()}, and
{\bf Prod()}.

\item {\bf jerasure\_04.cpp}: This does the exact same thing as {\bf jerasure\_03}, 
except it uses {\bf JER\_\-Matrix::Matrix\_\-To\_\-Bitmatrix()} to convert the 
Cauchy matrix to a bit-matrix, and then uses the bit-matrix operations to 
test invertibility and to invert the matrix.  Examples:

{\footnotesize \begin{verbatim}
UNIX> jerasure_04 4 3
The Cauchy Bit-Matrix:
010 101 001 111
011 111 101 100
101 011 010 110

101 010 111 001
111 011 100 101
011 101 110 010

001 111 010 101
101 100 011 111
010 110 101 011

111 001 101 010
100 101 111 011
110 010 011 101

Invertible: Yes

Inverse:
100 001 110 101
010 101 001 111
001 010 100 011

001 100 101 110
101 010 111 001
010 001 011 100

110 101 100 001
001 111 010 101
100 011 001 010

101 110 001 100
111 001 101 010
011 100 010 001

Inverse times matrix (should be identity):
100 000 000 000
010 000 000 000
001 000 000 000

000 100 000 000
000 010 000 000
000 001 000 000

000 000 100 000
000 000 010 000
000 000 001 000

000 000 000 100
000 000 000 010
000 000 000 001
UNIX>

UNIX> jerasure_04 5 3
The Cauchy Bit-Matrix:
010 101 001 111 011
011 111 101 100 110
101 011 010 110 111

101 010 111 001 110
111 011 100 101 001
011 101 110 010 100

001 111 010 101 100
101 100 011 111 010
010 110 101 011 001

111 001 101 010 000
100 101 111 011 000
110 010 011 101 000

011 110 100 000 010
110 001 010 000 011
111 100 001 000 101

Invertible: No

UNIX> 
\end{verbatim}}
This demonstrates usage of 
{\bf galois\_single\_divide()},
{\bf JER\_\-Matrix::Set()},
{\bf JER\_\-Matrix::Matrix\_\-To\_\-Bitmatrix()},
{\bf JER\_\-Matrix::Print()},
{\bf Inverse()}, and
{\bf Prod()}.

\end{itemize}

\section{Part 3 of the Library: Reed-Solomon Coding (reed\_sol.h)}
\label{src:reed-sol}

The files {\bf Reed\_sol.h} and {\bf reed\_sol.cpp} implement procedures that are specific to Vandermonde matrix-based Reed-Solomon coding, Cauchy matrix-based Reed-Solomon coding, and for Reed-Solomon coding optimized for RAID-6.  Refer to~\cite{p:97:rs,pd:05:rs} for a description of classic Reed-Solomon coding and to~\cite{a:07:mr6} for Reed-Solomon coding optimized for RAID-6.  Methods beginning with RS refer to Vandermonde based codings. The methods beginning with CRS are Cauchy based, and those beginning with RS\_R6 are opitimized for RAID-6. Where not specified, the parameters are as described in Section~\ref{sec:kernel}.

\subsection{Cauchy matrices}
We don't use the Cauchy matrices described in~\cite{px:06:ocr}, because there is
a simple heuristic that creates better matrices:

\begin{itemize}
\item Construct the usual Cauchy matrix~$M$
such that $M[i,j] = \frac{1}{i \oplus (m+j)}$, where division is over~$GF(2^w)$, 
$\oplus$ is XOR and the addition is regular integer addition. 
\item For each column~$j$, divide each element (in~$GF(2^w)$) by $M[0,j]$.  This
has the effect of turning each element in row 0 to one.
\item Next, for each row~$i >0$  of the matrix, do the following:
\begin{itemize}
\item Count the number of ones in the bit representation of the row.  
\item Count the number of ones in the bit representation of the row divided by 
element~$M[i,j]$ for each~$j$.
\item Whichever value of~$j$ gives the minimal number of ones, if it improves
the number of ones in the original row, divide row~$i$ by~$M[i,j]$.  
\end{itemize}
\end{itemize}

While this does not guarantee an optimal number of ones, it typically generates a 
good matrix.  For example, suppose~$k = m = w = 3$.  The matrix~$M$ is as follows:
\begin{center}
\begin{tabular}{|ccc|}
6 & 7 & 2 \\
5 & 2 & 7 \\
1 & 3 & 4 \\
\end{tabular}
\end{center}
First, we divide column 0 by 6, column 1 by 7 and column 2 by 2, to yield:
\begin{center}
\begin{tabular}{|ccc|}
1 & 1 & 1 \\
4 & 3 & 6 \\
3 & 7 & 2 \\
\end{tabular}
\end{center}
Now, we concentrate on row 1.  Its bitmatrix representation has 5+7+7 = 19 ones.
If we divide it by 4, the bitmatrix has 3+4+5 = 12 ones. 
If we divide it by 3, the bitmatrix has 4+3+4 = 11 ones. 
If we divide it by 6, the bitmatrix has 6+7+3 = 16 ones. 
So, we replace row 1 with row 1 divided by 3.

We do the same with row 2 and find that it will have the minimal number of
ones when it is divided by three.   The final
matrix is:
\begin{center}
\begin{tabular}{|ccc|}
1 & 1 & 1 \\
5 & 1 & 2 \\
1 & 4 & 7 \\
\end{tabular}
\end{center}
This matrix has 34 ones, a distinct improvement over the original matrix
that has 46 ones.  The best matrix in~\cite{px:06:ocr} has 39 ones.  This is
because the authors simply find the best~$X$ and~$Y$, and do not modify the
matrix after creating it.

\subsection{Reed-Solomon generators - reed\_sol.cpp}
The following are the methods used to generate matrices for Reed-Solomon coding:
\begin{itemize}
\item{\bf int CRS\_N\_Ones( int n, int w )}: Returns the number of ones in the bitmatrix representation of the number {\bf n}. The argument {\bf n} must exist in $GF(2^w)$.
\item{\bf JER\_Matrix *RS\_\-Nonsystematic\_\-Matrix(int n, int k, int w)}: Creates and returns a non-systematic Vandermonde matrix for Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-Nonsystematic\_\-Matrix()} returns failed. Returns NULL on failure.
\item{\bf JER\_Gen\_T *RS\_Nonsystematic\_Generator(int n, int k, int w)}: Creates and returns a generator containing a non-systematic Vandermonde matrix for Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-Nonsystematic\_\-Generator()} returns failed. Returns NULL on failure.
\item{\bf int RS\_Nonsystematic\_Generator(int n, int k, int w, JER\_Gen\_T \&g)}: Modifies {\bf g} to be a generator containing a non-systematic Vandermonde matrix for Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-Nonsystematic\_\-Generator()} returns failed. Return 0 on success, -1 on failure.
\item{\bf JER\_Matrix *RS\_Extended\_Matrix(int n, int k, int w)}: Creates and returns an extended systematic Vandermonde matrix for Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-Extended\_\-Matrix()} returns failed. Returns NULL on failure.
\item{\bf JER\_Gen\_T *RS\_Extended\_Generator(int n, int k, int w)}: Creates and returns a generator containing an extended Vandermonde matrix for Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-Extended\_\-Generator()} returns failed. Returns NULL on failure.
\item{\bf int RS\_Extended\_Generator(int n, int k, int w, JER\_Gen\_T \&g)}: Modifies {\bf g} to be a generator containing an extended Vandermonde matrix for Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-Extended\_\-Generator()} returns failed. Return 0 on success, -1 on failure.
\item{\bf JER\_Matrix *RS\_Classic\_Matrix(int n, int k, int w)}: Creates and returns an extended systematic Vandermonde matrix for Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-Classic\_\-Matrix()} returns failed. Returns NULL on failure.
\item{\bf JER\_Gen\_T *RS\_Classic\_Generator(int n, int k, int w)}: Creates and returns a generator containing a Vandermonde matrix for Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-Classic\_\-Generator()} returns failed. Returns NULL on failure.
\item{\bf int RS\_Classic\_Generator(int n, int k, int w, JER\_Gen\_T \&g)}: Modifies {\bf g} to be a generator containing a Vandermonde matrix for Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-Classic\_\-Generator()} returns failed. Return 0 on success, -1 on failure.
\item{\bf JER\_Gen\_T *RS\_R6\_Generator( int k, int w)}: Creates and returns a generator containing a matrix for RAID-6 Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-R6\_\-Generator()} returns failed. Returns NULL on failure.
\item{\bf int RS\_\-R6\_\-Generator(int k, int w, JER\_\-Gen\_\-T \&g)}: Modifies {\bf g} to be a generator containing a matrix for RAID-6 Reed-Solomon coding. If {\bf n},{\bf k} $> 2^w$, nothing is done and {\bf RS\_\-R6\_\-Generator()} returns failed. Return 0 on success, -1 on failure.
\item{\bf JER\_Gen\_T *CRS\_Generator(int k, int m, int w)}: Creates and returns a generator containing a Cauchy matrix for Reed-Solomon coding. If {\bf m} + {\bf k} $> 2^w$, nothing is done and {\bf CRS\_\-Generator()} returns failed. Returns NULL on failure.
\item{\bf int CRS\_\-Generator(int k, int m, int w, JER\_Gen\_T \&g)}: Modifies {\bf g} to be a generator containing a Cauchy matrix for Reed-Solomon coding. If {\bf m} + {\bf k} $> 2^w$, nothing is done and {\bf CRS\_\-Generator()} returns failed. Return 0 on success, -1 on failure.
\item{\bf JER\_Gen\_T *CRS\_XY\_Generator(int k, int m, int w, vector $\langle$int$\rangle$ \&X, vector $\langle$int$\rangle$ \&Y)}: Creates and returns a generator containing a Cauchy matrix created based off of the {\bf X} and {\bf Y} sets for Reed-Solomon coding. If {\bf m} + {\bf k} $> 2^w$, nothing is done and {\bf CRS\_\-XY\_\-Generator()} returns failed. Returns NULL on failure.
\item{\bf int CRS\_XY\_Generator(int k, int m, int w, vector $\langle$int$\rangle$ \&X, vector $\langle$int$\rangle$ \&Y, JER\_\-Gen\_\-T \&g)}: Modifies {\bf g} to be a generator containing a Cauchy matrix based off of the {\bf X} and {\bf Y} sets matrix for Reed-Solomon coding. If {\bf m} + {\bf k} $> 2^w$, nothing is done and {\bf CRS\_\-XY\_\-Generator()} returns failed. Return 0 on success, -1 on failure.	
\item{\bf int CRS\_\-Improve\_\-Generator(JER\_Gen\_T *g)}: Row reduces the matrix held by {\bf g} to minimize the number of ones in its bitmatrix representation.
\item{\bf JER\_\-Gen\_\-T *CRS\_\-Good\_\-Generator\_\-Bitmatrix(int k, int m, int w)}: Creates and returns a generator containing a Cauchy bitmatrix that has been improved. For {\bf m} = 2, the function returns an optimal bitmatrix. If {\bf m} + {\bf k} $> 2^w$, nothing is done and {\bf CRS\_\-Good\_\-Generator\_\-Bitmatrix()} returns failed. Returns NULL on failure.
\item{\bf int CRS\_Good\_Generator\_Bitmatrix(int k, int m, int w, JER\_Gen\_T \&g)}: Modifies {\bf g} to be a generator containing a Cauchy bitmatrix that has been improved. For {\bf m} = 2, the function returns an optimal bitmatrix. If {\bf m} + {\bf k} $> 2^w$, nothing is done and {\bf CRS\_\-Good\_\-Generator\_\-Bitmatrix()} returns failed. Returns 0 on success, -1 on failure.
\end{itemize}

\subsection{Example Programs}
\label{sec:ususe}

There are eleven example programs to demonstrate the use of the procedures in {\bf reed\_sol}.

\begin{itemize}

\item {\bf reed\_sol\_rs\_01.cpp}: This takes three parameters: $k$, $m$ and $w$.  It performs
a classic Reed-Solomon coding of~$k$ devices onto~$m$ devices, using a Vandermonde-based
distribution matrix in~$GF(2^w)$.  $w$ must be 8, 16 or 32.  Each device is set up to hold
{\bf 8} bytes.  It uses
{\bf RS\_\-Classic\_\-Generator()} to generate the distribution matrix, and
then procedures from {\bf jer\_\-slices.cpp} to perform the coding and decoding.

Example:
{\footnotesize \begin{verbatim}
UNIX> reed_sol_rs_01 7 7 8
Last m rows of the Distribution Matrix:

  1   1   1   1   1   1   1
  1 199 210 240 105 121 248
  1  70  91 245  56 142 167
  1 170 114  42  87  78 231
  1  38 236  53 233 175  65
  1  64 174 232  52 237  39
  1 187 104 210 211 105 186

Original data:

Data                                 Coding
D0  (up): c0 c9 fc 5f 6e b1 dd 15    C0  (down): 00 00 00 00 00 00 00 00
D1  (up): 91 67 6b 6f 0a e8 55 0c    C1  (down): 00 00 00 00 00 00 00 00
D2  (up): f2 11 95 64 d0 14 e5 49    C2  (down): 00 00 00 00 00 00 00 00
D3  (up): ae bb 33 2f 69 d1 99 58    C3  (down): 00 00 00 00 00 00 00 00
D4  (up): b4 46 5f 5f ba 16 dc 6f    C4  (down): 00 00 00 00 00 00 00 00
D5  (up): 3b f7 46 2d 48 08 18 39    C5  (down): 00 00 00 00 00 00 00 00
D6  (up): 5c f4 4e 21 0b 34 c3 5d    C6  (down): 00 00 00 00 00 00 00 00

Encoding complete:

Data                                 Coding
D0  (up): c0 c9 fc 5f 6e b1 dd 15    C0  (up): de 41 66 28 24 b6 f3 03
D1  (up): 91 67 6b 6f 0a e8 55 0c    C1  (up): 94 f8 b5 5e 55 94 b7 72
D2  (up): f2 11 95 64 d0 14 e5 49    C2  (up): 39 7b 52 ac 33 3b 2a 29
D3  (up): ae bb 33 2f 69 d1 99 58    C3  (up): 6e 92 59 73 af 8e 29 78
D4  (up): b4 46 5f 5f ba 16 dc 6f    C4  (up): fc be 8f ea 1f 84 a0 a8
D5  (up): 3b f7 46 2d 48 08 18 39    C5  (up): 32 89 7b 83 5d 44 2b 33
D6  (up): 5c f4 4e 21 0b 34 c3 5d    C6  (up): 19 73 3f b1 ae 72 18 91

Erased 7 random devices:

Data                                   Coding
D0  (up  ): c0 c9 fc 5f 6e b1 dd 15    C0  (down): 00 00 00 00 00 00 00 00
D1  (down): 00 00 00 00 00 00 00 00    C1  (up  ): 94 f8 b5 5e 55 94 b7 72
D2  (down): 00 00 00 00 00 00 00 00    C2  (down): 00 00 00 00 00 00 00 00
D3  (up  ): ae bb 33 2f 69 d1 99 58    C3  (down): 00 00 00 00 00 00 00 00
D4  (up  ): b4 46 5f 5f ba 16 dc 6f    C4  (up  ): fc be 8f ea 1f 84 a0 a8
D5  (up  ): 3b f7 46 2d 48 08 18 39    C5  (up  ): 32 89 7b 83 5d 44 2b 33
D6  (down): 00 00 00 00 00 00 00 00    C6  (down): 00 00 00 00 00 00 00 00

State of the system after decoding:

Data                                 Coding
D0  (up): c0 c9 fc 5f 6e b1 dd 15    C0  (up): de 41 66 28 24 b6 f3 03
D1  (up): 91 67 6b 6f 0a e8 55 0c    C1  (up): 94 f8 b5 5e 55 94 b7 72
D2  (up): f2 11 95 64 d0 14 e5 49    C2  (up): 39 7b 52 ac 33 3b 2a 29
D3  (up): ae bb 33 2f 69 d1 99 58    C3  (up): 6e 92 59 73 af 8e 29 78
D4  (up): b4 46 5f 5f ba 16 dc 6f    C4  (up): fc be 8f ea 1f 84 a0 a8
D5  (up): 3b f7 46 2d 48 08 18 39    C5  (up): 32 89 7b 83 5d 44 2b 33
D6  (up): 5c f4 4e 21 0b 34 c3 5d    C6  (up): 19 73 3f b1 ae 72 18 91

UNIX> 
\end{verbatim}}
This demonstrates usage of 
{\bf RS\_\-Classic\_\-Generator()},
{\bf JER\_\-Matrix::Print()},
{\bf JER\_\-Slices::Encode()} and
{\bf JER\_\-Slices::Decode()}.

\item {\bf reed\_sol\_rs\_02.cpp}: This takes three parameters: $k$, $m$ and $w$.  It creates
and prints three matrices in~$GF(2^w)$: 
\begin{enumerate}
\item A $(k+m) \times k$ non-systematic Vandermonde Matrix.
\item The $(k+m) \times k$ extended Vandermonde matrix created by converting the non-systematic Vandermonde matrix into one where the first~$k$ rows are an identity matrix.  Then
row~$k$ is converted so that it is all ones, and the first column is also converted 
so that it is all ones.
\item The $m \times k$ classic Vandermonde coding matrix, which is last~$m$ rows of the above matrix.
This is the matrix which is passed to the encoding/decoding procedures of~{\bf jer\_\-slices.cpp}.
Note that the first row of this matrix is all ones, so the generator's {\bf PDrive} argument will be set to true.
\end{enumerate}
Note also that~$w$ may have any value from 1 to 32.

Example:
{\footnotesize \begin{verbatim}
UNIX> reed_sol_rs_02 6 4 11
Non-systematic Vandermonde Matrix:

   1    0    0    0    0    0
   1    1    1    1    1    1
   1    2    4    8   16   32
   1    3    5   15   17   51
   1    4   16   64  256 1024
   1    5   17   85  257 1285
   1    6   20  120  272 1632
   1    7   21  107  273 1911
   1    8   64  512   10   80
   0    0    0    0    0    1

Vandermonde Extended Matrix:

   1    0    0    0    0    0
   0    1    0    0    0    0
   0    0    1    0    0    0
   0    0    0    1    0    0
   0    0    0    0    1    0
   0    0    0    0    0    1
   1    1    1    1    1    1
   1 1879 1231 1283  682 1538
   1 1366 1636 1480  683  934
   1 1023 2045 1027 2044 1026

Vandermonde Classic Coding Matrix:

   1    1    1    1    1    1
   1 1879 1231 1283  682 1538
   1 1366 1636 1480  683  934
   1 1023 2045 1027 2044 1026

UNIX> 
\end{verbatim}}
This demonstrates usage of 
{\bf RS\_\-Nonsystematic\_\-Matrix()},
{\bf RS\_\-Extended\_\-Matrix()},
{\bf RS\_\-Classic\_\-Matrix()}, and
{\bf JER\_\-Matrix::Print()}.

\item {\bf reed\_sol\_rs\_r6\_01.cpp}: This takes two parameters: $k$ and $w$.  It performs
RAID-6 coding using Anvin's optimization~\cite{a:07:mr6} in~$GF(2^{w})$, where~$w$
must be 8, 16 or 32.  It then decodes using {\bf JER\_\-Slices::Decode()}.

Example:
{\footnotesize \begin{verbatim}
UNIX> reed_sol_rs_r6_01 9 8
Last 2 rows of the Distribution Matrix:

  1   1   1   1   1   1   1   1   1
  1   2   4   8  16  32  64 128  29

Original data:

Data                                 Coding
D0  (up): c0 c9 fc 5f 6e b1 dd 15    C0  (down): 00 00 00 00 00 00 00 00
D1  (up): 91 67 6b 6f 0a e8 55 0c    C1  (down): 00 00 00 00 00 00 00 00
D2  (up): f2 11 95 64 d0 14 e5 49    
D3  (up): ae bb 33 2f 69 d1 99 58    
D4  (up): b4 46 5f 5f ba 16 dc 6f    
D5  (up): 3b f7 46 2d 48 08 18 39    
D6  (up): 5c f4 4e 21 0b 34 c3 5d    
D7  (up): 66 da 6d 63 ea 37 78 32    
D8  (up): 81 6d b3 49 83 1c 2a 6c    

Encoding complete:

Data                                 Coding
D0  (up): c0 c9 fc 5f 6e b1 dd 15    C0  (up): 39 f6 b8 02 4d 9d a1 5d
D1  (up): 91 67 6b 6f 0a e8 55 0c    C1  (up): 7d a6 d5 a0 23 d8 17 ed
D2  (up): f2 11 95 64 d0 14 e5 49    
D3  (up): ae bb 33 2f 69 d1 99 58    
D4  (up): b4 46 5f 5f ba 16 dc 6f    
D5  (up): 3b f7 46 2d 48 08 18 39    
D6  (up): 5c f4 4e 21 0b 34 c3 5d    
D7  (up): 66 da 6d 63 ea 37 78 32    
D8  (up): 81 6d b3 49 83 1c 2a 6c    

Erased 2 random devices:

Data                                   Coding
D0  (up  ): c0 c9 fc 5f 6e b1 dd 15    C0  (up): 39 f6 b8 02 4d 9d a1 5d
D1  (up  ): 91 67 6b 6f 0a e8 55 0c    C1  (up): 7d a6 d5 a0 23 d8 17 ed
D2  (down): 00 00 00 00 00 00 00 00    
D3  (up  ): ae bb 33 2f 69 d1 99 58    
D4  (up  ): b4 46 5f 5f ba 16 dc 6f    
D5  (up  ): 3b f7 46 2d 48 08 18 39    
D6  (up  ): 5c f4 4e 21 0b 34 c3 5d    
D7  (up  ): 66 da 6d 63 ea 37 78 32    
D8  (down): 00 00 00 00 00 00 00 00    

State of the system after decoding:

Data                                 Coding
D0  (up): c0 c9 fc 5f 6e b1 dd 15    C0  (up): 39 f6 b8 02 4d 9d a1 5d
D1  (up): 91 67 6b 6f 0a e8 55 0c    C1  (up): 7d a6 d5 a0 23 d8 17 ed
D2  (up): f2 11 95 64 d0 14 e5 49    
D3  (up): ae bb 33 2f 69 d1 99 58    
D4  (up): b4 46 5f 5f ba 16 dc 6f    
D5  (up): 3b f7 46 2d 48 08 18 39    
D6  (up): 5c f4 4e 21 0b 34 c3 5d    
D7  (up): 66 da 6d 63 ea 37 78 32    
D8  (up): 81 6d b3 49 83 1c 2a 6c    

UNIX> 
\end{verbatim}}
This demonstrates usage of 
{\bf RS\_\-R6\_\-Generator()},
{\bf JER\_\-Matrix::Print()},
{\bf JER\_\-Slices::Encode()}, and
{\bf JER\_\-Slices::Decode()}.

\item {\bf reed\_sol\_rs\_r6\_02.cpp}: This takes two parameters: $k$ and $w$, and performs
a simple RAID-6 example using a schedule cache.  Again, {\em packetsize} is
{\bf 8} bytes.  It sets up a RAID-6
coding matrix whose first row is composed of ones, and where the
element in column~$j$ of the second row is equal to~$2^j$ in~$GF(2^w)$.
It converts this to a bit-matrix and creates a smart encoding schedule
and a schedule cache for decoding.

It then sets the two coding devices as the erased devices, and encodes using the smart shedule. Next it deletes two random devices and uses the schedule cache to decode them. Finally, it deletes the first coding devices and recalculates it using
{\bf JER\_\-Slices::Do\_\-Parity()} to demonstrate that procedure.

Example:
{\footnotesize \begin{verbatim}
UNIX> reed_sol_rs_r6_02 5 3
Last (m * w) rows of the Binary Distribution Matrix:

100 100 100 100 100
010 010 010 010 010
001 001 001 001 001

100 001 010 101 011
010 101 011 111 110
001 010 101 011 111

Original data:

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (down): p0 :0000000000000000
          p1 :05542a27169c39e2                p1 :0000000000000000
          p2 :2eab49560bb0b8b4                p2 :0000000000000000
D1  (up): p0 :0bd068c93e5d224d    C1  (down): p0 :0000000000000000
          p1 :436c8d9c3a2adfda                p1 :0000000000000000
          p2 :1dd8ca796a67c4f1                p2 :0000000000000000
D2  (up): p0 :7742fa2948b62d69    
          p1 :472e195d0681a900    
          p2 :622ebb7e026bccdf    
D3  (up): p0 :204d531e262b5331    
          p1 :7020241c440a0e2a    
          p2 :75cb1c4c41f9a5e1    
D4  (up): p0 :67bc26ff181e279e    
          p1 :7172c06f4909e153    
          p2 :09d3bfba685ae502    

Smart Schedule Encoding Complete: - 248 XOR'd bytes

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (up): p0 :3b63e70148fe319d
          p1 :05542a27169c39e2              p1 :00445a952734a041
          p2 :2eab49560bb0b8b4              p2 :2d459ba74a1ff079
D1  (up): p0 :0bd068c93e5d224d    C1  (up): p0 :77d1e3a32a47d566
          p1 :436c8d9c3a2adfda              p1 :0534a76a348384b6
          p2 :1dd8ca796a67c4f1              p2 :625de4e747f90edc
D2  (up): p0 :7742fa2948b62d69    
          p1 :472e195d0681a900    
          p2 :622ebb7e026bccdf    
D3  (up): p0 :204d531e262b5331    
          p1 :7020241c440a0e2a    
          p2 :75cb1c4c41f9a5e1    
D4  (up): p0 :67bc26ff181e279e    
          p1 :7172c06f4909e153    
          p2 :09d3bfba685ae502    

Deleted both coding drives:

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (down): p0 :0000000000000000
          p1 :05542a27169c39e2                p1 :0000000000000000
          p2 :2eab49560bb0b8b4                p2 :0000000000000000
D1  (up): p0 :0bd068c93e5d224d    C1  (down): p0 :0000000000000000
          p1 :436c8d9c3a2adfda                p1 :0000000000000000
          p2 :1dd8ca796a67c4f1                p2 :0000000000000000
D2  (up): p0 :7742fa2948b62d69    
          p1 :472e195d0681a900    
          p2 :622ebb7e026bccdf    
D3  (up): p0 :204d531e262b5331    
          p1 :7020241c440a0e2a    
          p2 :75cb1c4c41f9a5e1    
D4  (up): p0 :67bc26ff181e279e    
          p1 :7172c06f4909e153    
          p2 :09d3bfba685ae502    

Decoded using the smart decoding schedules: - 248 XOR'd bytes

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (up): p0 :3b63e70148fe319d
          p1 :05542a27169c39e2              p1 :00445a952734a041
          p2 :2eab49560bb0b8b4              p2 :2d459ba74a1ff079
D1  (up): p0 :0bd068c93e5d224d    C1  (up): p0 :77d1e3a32a47d566
          p1 :436c8d9c3a2adfda              p1 :0534a76a348384b6
          p2 :1dd8ca796a67c4f1              p2 :625de4e747f90edc
D2  (up): p0 :7742fa2948b62d69    
          p1 :472e195d0681a900    
          p2 :622ebb7e026bccdf    
D3  (up): p0 :204d531e262b5331    
          p1 :7020241c440a0e2a    
          p2 :75cb1c4c41f9a5e1    
D4  (up): p0 :67bc26ff181e279e    
          p1 :7172c06f4909e153    
          p2 :09d3bfba685ae502    

Erased 2 random devices:

Data                                Coding
D0  (up  ): p0 :0000000000204a16    C0  (up): p0 :3b63e70148fe319d
            p1 :05542a27169c39e2              p1 :00445a952734a041
            p2 :2eab49560bb0b8b4              p2 :2d459ba74a1ff079
D1  (down): p0 :0000000000000000    C1  (up): p0 :77d1e3a32a47d566
            p1 :0000000000000000              p1 :0534a76a348384b6
            p2 :0000000000000000              p2 :625de4e747f90edc
D2  (up  ): p0 :7742fa2948b62d69    
            p1 :472e195d0681a900    
            p2 :622ebb7e026bccdf    
D3  (up  ): p0 :204d531e262b5331    
            p1 :7020241c440a0e2a    
            p2 :75cb1c4c41f9a5e1    
D4  (down): p0 :0000000000000000    
            p1 :0000000000000000    
            p2 :0000000000000000    

Decoded using the dumb decoding schedules: - 384 XOR'd bytes

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (up): p0 :3b63e70148fe319d
          p1 :05542a27169c39e2              p1 :00445a952734a041
          p2 :2eab49560bb0b8b4              p2 :2d459ba74a1ff079
D1  (up): p0 :0bd068c93e5d224d    C1  (up): p0 :77d1e3a32a47d566
          p1 :436c8d9c3a2adfda              p1 :0534a76a348384b6
          p2 :1dd8ca796a67c4f1              p2 :625de4e747f90edc
D2  (up): p0 :7742fa2948b62d69    
          p1 :472e195d0681a900    
          p2 :622ebb7e026bccdf    
D3  (up): p0 :204d531e262b5331    
          p1 :7020241c440a0e2a    
          p2 :75cb1c4c41f9a5e1    
D4  (up): p0 :67bc26ff181e279e    
          p1 :7172c06f4909e153    
          p2 :09d3bfba685ae502    

Erased first coding device:

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (down): p0 :0000000000000000
          p1 :05542a27169c39e2                p1 :0000000000000000
          p2 :2eab49560bb0b8b4                p2 :0000000000000000
D1  (up): p0 :0bd068c93e5d224d    C1  (up  ): p0 :77d1e3a32a47d566
          p1 :436c8d9c3a2adfda                p1 :0534a76a348384b6
          p2 :1dd8ca796a67c4f1                p2 :625de4e747f90edc
D2  (up): p0 :7742fa2948b62d69    
          p1 :472e195d0681a900    
          p2 :622ebb7e026bccdf    
D3  (up): p0 :204d531e262b5331    
          p1 :7020241c440a0e2a    
          p2 :75cb1c4c41f9a5e1    
D4  (up): p0 :67bc26ff181e279e    
          p1 :7172c06f4909e153    
          p2 :09d3bfba685ae502    

Re-encoded coding device 0 with JER_Slices::Do_Parity() - 96 XOR'd bytes

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (down): p0 :3b63e70148fe319d
          p1 :05542a27169c39e2                p1 :00445a952734a041
          p2 :2eab49560bb0b8b4                p2 :2d459ba74a1ff079
D1  (up): p0 :0bd068c93e5d224d    C1  (up  ): p0 :77d1e3a32a47d566
          p1 :436c8d9c3a2adfda                p1 :0534a76a348384b6
          p2 :1dd8ca796a67c4f1                p2 :625de4e747f90edc
D2  (up): p0 :7742fa2948b62d69    
          p1 :472e195d0681a900    
          p2 :622ebb7e026bccdf    
D3  (up): p0 :204d531e262b5331    
          p1 :7020241c440a0e2a    
          p2 :75cb1c4c41f9a5e1    
D4  (up): p0 :67bc26ff181e279e    
          p1 :7172c06f4909e153    
          p2 :09d3bfba685ae502

UNIX>
\end{verbatim}}
This demonstrates usage of
{\bf RS\_\-R6\_\-Generator()},
{\bf CRS\_\-Convert\_\-To\_\-Bitmatrix()},
{\bf JER\_\-Matrix::Print()},
{\bf JER\_\-Gen\_\-T::Create\_\-Encode\_\-Schedule()},
{\bf JER\_\-Slices::Encode()},
{\bf JER\_\-Slices::Add\_\-Drive\_\-Failure()},
{\bf JER\_\-Gen\_\-T::Create\_\-R6\_\-Schedules()},
{\bf JER\_\-Slices::Decode()}, and
{\bf JER\_\-Slices::Do\_\-Parity()}.

\item {\bf reed\_sol\_crs\_01.cpp}: 
This takes four parameters: $k$, $m$, $w$ and $size$, and performs
a classic Cauchy Reed-Solomon coding example in~$GF(2^w)$.  $w$ must be either 8, 16 or
32, and the sum~$k+m$ must be less than or equal to $2^w$.
The total number of bytes for each device is given by $size$ which must be
a multiple of~{\bf 8}.
It first sets up an~$m \times k$ Cauchy coding matrix where element~$i,j$ is:
\[ \frac{1}{i \oplus (m+j)} \]
where division is in~$GF(2^w)$, $\oplus$ is XOR, and addition is standard integer
addition.  It prints out these~$m$ rows.  
The program then creates $k$ data devices each with $size$ bytes of random 
data and encodes them into $m$ coding devices using
{\bf JER\_\-Slices::Encode()}.  It prints out the data and coding in hexadecimal--
one byte is represented by 2 hex digits.
Next, it erases~$m$ random devices from the collection of data and coding devices, and prints 
the resulting state.
Then it decodes the erased devices using
{\bf JER\_\-Slices::Decode()} and prints the restored state.
Next, it shows what the decoding
matrix looks like when the first~$m$ devices are erased.  This matrix is the inverse of the
last $k$ rows of the distribution matrix.  And finally, it uses {\bf JER\_\-Slices::Make\_\-Decoding\_\-Matrix()} and {\bf JER\_\-Slices::Dotprod()} to show how to explicitly calculate the first data device from the others when the first~$m$ devices have been erased.

Here is an example for $w=8$ with 3 data devices and 4 coding devices each 
with a size of 8 bytes:
{\footnotesize \begin{verbatim}
UNIX> reed_sol_crs_01 3 4 8 8
The Coding Matrix (the last m rows of the Distribution Matrix):

 71 167 122
167  71 186
122 186  71
186 122 167

Original data:

Data                                 Coding
D0  (up): c0 c9 fc 5f 6e b1 dd 15    C0  (down): 00 00 00 00 00 00 00 00
D1  (up): 91 67 6b 6f 0a e8 55 0c    C1  (down): 00 00 00 00 00 00 00 00
D2  (up): f2 11 95 64 d0 14 e5 49    C2  (down): 00 00 00 00 00 00 00 00
                                     C3  (down): 00 00 00 00 00 00 00 00
Encoding complete:

Data                                 Coding
D0  (up): c0 c9 fc 5f 6e b1 dd 15    C0  (up): 90 45 c6 d3 44 ae 35 d3
D1  (up): 91 67 6b 6f 0a e8 55 0c    C1  (up): 8e 38 4c 6c 52 a2 23 02
D2  (up): f2 11 95 64 d0 14 e5 49    C2  (up): 18 90 5d 4a 02 25 73 42
                                     C3  (up): df 93 97 a7 17 7c 44 41

Erased 4 random devices:

Data                                   Coding
D0  (down): 00 00 00 00 00 00 00 00    C0  (down): 00 00 00 00 00 00 00 00
D1  (up  ): 91 67 6b 6f 0a e8 55 0c    C1  (up  ): 8e 38 4c 6c 52 a2 23 02
D2  (up  ): f2 11 95 64 d0 14 e5 49    C2  (down): 00 00 00 00 00 00 00 00
                                       C3  (down): 00 00 00 00 00 00 00 00

State of the system after decoding:

Data                                 Coding
D0  (up): c0 c9 fc 5f 6e b1 dd 15    C0  (up): 90 45 c6 d3 44 ae 35 d3
D1  (up): 91 67 6b 6f 0a e8 55 0c    C1  (up): 8e 38 4c 6c 52 a2 23 02
D2  (up): f2 11 95 64 d0 14 e5 49    C2  (up): 18 90 5d 4a 02 25 73 42
                                     C3  (up): df 93 97 a7 17 7c 44 41

Erased the first 4 devices

Data                                   Coding
D0  (down): 00 00 00 00 00 00 00 00    C0  (down): 00 00 00 00 00 00 00 00
D1  (down): 00 00 00 00 00 00 00 00    C1  (up  ): 8e 38 4c 6c 52 a2 23 02
D2  (down): 00 00 00 00 00 00 00 00    C2  (up  ): 18 90 5d 4a 02 25 73 42
                                       C3  (up  ): df 93 97 a7 17 7c 44 41

Here is the decoding matrix:

130  25 182
252 221  25
108 252 130

And dm_ids:

 4 5 6

After calling Dotprod, we calculate the value of device #0 to be:

D0 : c0 c9 fc 5f 6e b1 dd 15

UNIX>
\end{verbatim}}

Referring back to the conceptual model in Figure 3, it should be clear 
in this encoding how the first $w$ bits of $C_0$
are calculated from the first $w$ bits of each data device:
\[
	\mbox{ byte } 0 \mbox{ of } C_0 = 
	(71 \times \mbox{ byte } 0 \mbox{ of } D_0) \oplus  
	(167 \times \mbox{ byte } 0 \mbox{ of } D_1) \oplus
	(122 \times \mbox{ byte } 0 \mbox{ of } D_2) 
\]
	where multiplication is in $GF (2^8)$.
	
However, keep in mind that the implementation actually performs dot products 
on groups of bytes at a time.  So in this example, where each device holds 8 bytes,
the dot product is actually:
\[
	8 \mbox{ bytes of } C_0 =
	(71 \times 8 \mbox{ bytes of } D_0) \oplus  
	(167 \times 8 \mbox{ bytes of } D_1) \oplus
	(122 \times 8 \mbox{ bytes of } D_2) 
\]
This is accomplished using {\bf galois\_\-w08\_\-region\_\-multiply()}.

Here is a similar example, this time with $w=16$ and each device holding 16 bytes:
{\footnotesize \begin{verbatim}
UNIX> reed_sol_crs_01 3 4 16 16
The Coding Matrix (the last m rows of the Distribution Matrix):

52231 20482 30723
20482 52231 27502
30723 27502 52231
27502 30723 20482

Original data:

Data                                                 Coding
D0  (up): c0c9 fc5f 6eb1 dd15 9167 6b6f 0ae8 550c    C0  (down): 0000 0000 0000 0000 0000 0000 0000 0000
D1  (up): f211 9564 d014 e549 aebb 332f 69d1 9958    C1  (down): 0000 0000 0000 0000 0000 0000 0000 0000
D2  (up): b446 5f5f ba16 dc6f 3bf7 462d 4808 1839    C2  (down): 0000 0000 0000 0000 0000 0000 0000 0000
                                                     C3  (down): 0000 0000 0000 0000 0000 0000 0000 0000

Encoding complete:

Data                                                 Coding
D0  (up): c0c9 fc5f 6eb1 dd15 9167 6b6f 0ae8 550c    C0  (up): 8b79 e6cb ab06 4bcc b303 e10b 068b 1576
D1  (up): f211 9564 d014 e549 aebb 332f 69d1 9958    C1  (up): 7c5b 6194 7851 e1f5 9db9 340c 6181 a121
D2  (up): b446 5f5f ba16 dc6f 3bf7 462d 4808 1839    C2  (up): 41e2 4d35 a59b 8c16 0608 a65b d8d3 dcf1
                                                     C3  (up): d106 470e d782 63f9 f8e2 1b1e 47de 019c

Erased 4 random devices:

Data                                                   Coding
D0  (up  ): c0c9 fc5f 6eb1 dd15 9167 6b6f 0ae8 550c    C0  (down): 0000 0000 0000 0000 0000 0000 0000 0000
D1  (down): 0000 0000 0000 0000 0000 0000 0000 0000    C1  (down): 0000 0000 0000 0000 0000 0000 0000 0000
D2  (down): 0000 0000 0000 0000 0000 0000 0000 0000    C2  (up  ): 41e2 4d35 a59b 8c16 0608 a65b d8d3 dcf1
                                                       C3  (up  ): d106 470e d782 63f9 f8e2 1b1e 47de 019c

State of the system after decoding:

Data                                                 Coding
D0  (up): c0c9 fc5f 6eb1 dd15 9167 6b6f 0ae8 550c    C0  (up): 8b79 e6cb ab06 4bcc b303 e10b 068b 1576
D1  (up): f211 9564 d014 e549 aebb 332f 69d1 9958    C1  (up): 7c5b 6194 7851 e1f5 9db9 340c 6181 a121
D2  (up): b446 5f5f ba16 dc6f 3bf7 462d 4808 1839    C2  (up): 41e2 4d35 a59b 8c16 0608 a65b d8d3 dcf1
                                                     C3  (up): d106 470e d782 63f9 f8e2 1b1e 47de 019c

Erased the first 4 devices

Data                                                   Coding
D0  (down): 0000 0000 0000 0000 0000 0000 0000 0000    C0  (down): 0000 0000 0000 0000 0000 0000 0000 0000
D1  (down): 0000 0000 0000 0000 0000 0000 0000 0000    C1  (up  ): 7c5b 6194 7851 e1f5 9db9 340c 6181 a121
D2  (down): 0000 0000 0000 0000 0000 0000 0000 0000    C2  (up  ): 41e2 4d35 a59b 8c16 0608 a65b d8d3 dcf1
                                                       C3  (up  ): d106 470e d782 63f9 f8e2 1b1e 47de 019c

Here is the decoding matrix:

  130   260   427
  252   448   260
  108   252   130

And dm_ids:

 4 5 6

After calling JER_Slices::Dotprod(), we calculate the value of device #0 to be:

D0 : c0c9 fc5f 6eb1 dd15 9167 6b6f 0ae8 550c

UNIX>
\end{verbatim}}

In this encoding, the 8 16-bit half-words of $C_0$ are calculated as:
\[
	(52231 \times 8 \mbox{ half-words of } D_0) \oplus 
	(20482 \times 8 \mbox{ half-words of } D_1) \oplus 
	(30723 \times 8 \mbox{ half-words of } D_2)
\]

using {\bf galois\_\-w16\_\-region\_multiply()}.

This program demonstrates usage of
{\bf CRS\_\-Generator()}, 
{\bf JER\_\-Matrix::Print()},
{\bf JER\_\-Slices::Encode()},
{\bf JER\_\-Slices::Decode()},
{\bf JER\_\-Slices::Add\_\-Drive\_\-Failure()},
{\bf JER\_\-Slices::Make\_\-Decoding\_\-Matrix()}, and
{\bf JER\_\-Slices::Dotprod()}.

\item {\bf reed\_sol\_crs\_02.cpp}: 
This takes four parameters: $k$, $m$, $w$ and {\em packetsize}, and 
performs a similar example to {\bf reed\_sol\_crs\_01}, except it converts the Cauchy coding matrix to a bit-matrix.
$k+m$ must be less than or equal to $2^w$ and {\em packetsize} must be a multiple
of {\bf 8}.
It sets up each device to hold a total of $w * packetsize$ bytes.
Here, packets are numbered $p_0$ through $p_{w-1}$ for each device.
It then performs the same encoding and decoding as the previous example but
with the corresponding bit-matrix procedures.

Here is a run with 3 data devices and 4 coding devices with $w=3$ and
a {\em packetsize} of 8 bytes.  (Each device will hold $3 * 8 = 24$ bytes.)
{\footnotesize \begin{verbatim}
UNIX> reed_sol_crs_02 3 4 3 8
Last (m * w) rows of the Binary Distribution Matrix:

111 001 101
100 101 111
110 010 011

001 111 010
101 100 011
010 110 101

101 010 111
111 011 100
011 101 110

010 101 001
011 111 101
101 011 010

Original data:

Data                              Coding
D0  (up): p0 :15ddb16e5ffcc9c0    C0  (down): p0 :0000000000000000
          p1 :0c55e80a6f6b6791                p1 :0000000000000000
          p2 :49e514d0649511f2                p2 :0000000000000000
D1  (up): p0 :5899d1692f33bbae    C1  (down): p0 :0000000000000000
          p1 :6fdc16ba5f5f46b4                p1 :0000000000000000
          p2 :391808482d46f73b                p2 :0000000000000000
D2  (up): p0 :5dc3340b214ef45c    C2  (down): p0 :0000000000000000
          p1 :327837ea636dda66                p1 :0000000000000000
          p2 :6c2a1c8349b36d81                p2 :0000000000000000
                                  C3  (down): p0 :0000000000000000
                                              p1 :0000000000000000
                                              p2 :0000000000000000

Encoding complete:

Data                              Coding
D0  (up): p0 :15ddb16e5ffcc9c0    C0  (up): p0 :589c6d7411b9d145
          p1 :0c55e80a6f6b6791              p1 :77cd772d5619c6ee
          p2 :49e514d0649511f2              p2 :280664b745165f02
D1  (up): p0 :5899d1692f33bbae    C1  (up): p0 :75c0eca15ad2c1b5
          p1 :6fdc16ba5f5f46b4              p1 :5af35fbe3e84d47b
          p2 :391808482d46f73b              p2 :0af9075177fa0356
D2  (up): p0 :5dc3340b214ef45c    C2  (up): p0 :3075ac666fa6dd3d
          p1 :327837ea636dda66              p1 :5b6a674d0755fa70
          p2 :6c2a1c8349b36d81              p2 :4b8a261a4ba814cc
                                  C3  (up): p0 :01fe2da824ad4685
                                            p1 :7a041bc93e29e59f
                                            p2 :38848ca62a1db3db

Erased 4 random devices:

Data                                Coding
D0  (down): p0 :0000000000000000    C0  (down): p0 :0000000000000000
            p1 :0000000000000000                p1 :0000000000000000
            p2 :0000000000000000                p2 :0000000000000000
D1  (up  ): p0 :5899d1692f33bbae    C1  (up  ): p0 :75c0eca15ad2c1b5
            p1 :6fdc16ba5f5f46b4                p1 :5af35fbe3e84d47b
            p2 :391808482d46f73b                p2 :0af9075177fa0356
D2  (down): p0 :0000000000000000    C2  (up  ): p0 :3075ac666fa6dd3d
            p1 :0000000000000000                p1 :5b6a674d0755fa70
            p2 :0000000000000000                p2 :4b8a261a4ba814cc
                                    C3  (down): p0 :0000000000000000
                                                p1 :0000000000000000
                                                p2 :0000000000000000

State of the system after decoding:

Data                              Coding
D0  (up): p0 :15ddb16e5ffcc9c0    C0  (up): p0 :589c6d7411b9d145
          p1 :0c55e80a6f6b6791              p1 :77cd772d5619c6ee
          p2 :49e514d0649511f2              p2 :280664b745165f02
D1  (up): p0 :5899d1692f33bbae    C1  (up): p0 :75c0eca15ad2c1b5
          p1 :6fdc16ba5f5f46b4              p1 :5af35fbe3e84d47b
          p2 :391808482d46f73b              p2 :0af9075177fa0356
D2  (up): p0 :5dc3340b214ef45c    C2  (up): p0 :3075ac666fa6dd3d
          p1 :327837ea636dda66              p1 :5b6a674d0755fa70
          p2 :6c2a1c8349b36d81              p2 :4b8a261a4ba814cc
                                  C3  (up): p0 :01fe2da824ad4685
                                            p1 :7a041bc93e29e59f
                                            p2 :38848ca62a1db3db

Erased the first 4 devices

Data                                Coding
D0  (down): p0 :0000000000000000    C0  (down): p0 :0000000000000000
            p1 :0000000000000000                p1 :0000000000000000
            p2 :0000000000000000                p2 :0000000000000000
D1  (down): p0 :0000000000000000    C1  (up  ): p0 :75c0eca15ad2c1b5
            p1 :0000000000000000                p1 :5af35fbe3e84d47b
            p2 :0000000000000000                p2 :0af9075177fa0356
D2  (down): p0 :0000000000000000    C2  (up  ): p0 :3075ac666fa6dd3d
            p1 :0000000000000000                p1 :5b6a674d0755fa70
            p2 :0000000000000000                p2 :4b8a261a4ba814cc
                                    C3  (up  ): p0 :01fe2da824ad4685
                                                p1 :7a041bc93e29e59f
                                                p2 :38848ca62a1db3db

Here is the decoding matrix:

101 011 010
111 110 011
011 111 101

001 011 011
101 110 110
010 111 111

110 001 101
001 101 111
100 010 011

And dm_ids:

 4 5 6

After calling JER_Slices::Dotprod(), we calculate the value of device #0 to be:

D0 :
p0: 15ddb16e5ffcc9c0
p1: 0c55e80a6f6b6791
p2: 49e514d0649511f2

UNIX>
\end{verbatim}}
In this encoding, the first packet of $C_0$ is computed according to the 
six ones in the first row of the coding matrix:
\[
C_0p_0 = D_0p_0 \oplus D_0p_1 \oplus D_0p_2 \oplus D_1p_2 \oplus D_2p_0 \oplus D_2p_2
\]
These dot-products are accomplished with {\bf galois\_\-region\_\-xor() }.

This program demonstrates usage of 
{\bf CRS\_\-Generator()}, 
{\bf CRS\_\-Convert\_\-To\_\-Bitmatrix()},
{\bf JER\_\-Matrix::Print()},
{\bf JER\_\-Slices::Encode()},
{\bf JER\_\-Slices::Decode()},
{\bf JER\_\-Slices::Add\_\-Drive\_\-Failure()},
{\bf JER\_\-Slices::Make\_\-Decoding\_\-Matrix()}, and
{\bf JER\_\-Slices::Dotprod()}.

\item {\bf reed\_sol\_crs\_03.cpp}: This takes three parameters: $k$, $m$ and $w$.  It performs
the same coding/decoding as in {\bf reed\_sol\_crs\_02}, except it uses bit-matrix scheduling
instead of bit-matrix operations.  The {\em packetsize} is set at {\bf 8} bytes.
It creates a ``dumb'' and ``smart'' schedule for 
encoding, encodes with them and prints out how many XORs each took.  The smart schedule
will outperform the dumb one.

Finally, it erases~$m$ random devices and decodes with {\bf JER\_\-Slices::Decode\_\-Schedule\_\-Lazy()}. It decodes once with a smart schedule and once with a dumb schedule.

Example:
{\footnotesize \begin{verbatim}
UNIX> reed_sol_crs_03 3 4 3
Last (m * w) rows of the Binary Distribution Matrix:

111 001 101
100 101 111
110 010 011

001 111 010
101 100 011
010 110 101

101 010 111
111 011 100
011 101 110

010 101 001
011 111 101
101 011 010

Original data:

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (down): p0 :0000000000000000
          p1 :05542a27169c39e2                p1 :0000000000000000
          p2 :2eab49560bb0b8b4                p2 :0000000000000000
D1  (up): p0 :0bd068c93e5d224d    C1  (down): p0 :0000000000000000
          p1 :436c8d9c3a2adfda                p1 :0000000000000000
          p2 :1dd8ca796a67c4f1                p2 :0000000000000000
D2  (up): p0 :7742fa2948b62d69    C2  (down): p0 :0000000000000000
          p1 :472e195d0681a900                p1 :0000000000000000
          p2 :622ebb7e026bccdf                p2 :0000000000000000
                                  C3  (down): p0 :0000000000000000
                                              p1 :0000000000000000
                                              p2 :0000000000000000

Dumb Schedule Encoding Complete: - 432 XOR'd bytes

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (up): p0 :234be85f3db6ee07
          p1 :05542a27169c39e2              p1 :444afaba1846e41c
          p2 :2eab49560bb0b8b4              p2 :63380598287cc9f1
D1  (up): p0 :0bd068c93e5d224d    C1  (up): p0 :3ce17f27632128d2
          p1 :436c8d9c3a2adfda              p1 :007b83bc3127b530
          p2 :1dd8ca796a67c4f1              p2 :58848e25583625c3
D2  (up): p0 :7742fa2948b62d69    C2  (up): p0 :3f859cc07de665ce
          p1 :472e195d0681a900              p1 :0209debd05f7fd02
          p2 :622ebb7e026bccdf              p2 :0d9b22b50721e383
                                  C3  (up): p0 :717233e940cd1381
                                            p1 :6bf70d0a39e15986
                                            p2 :373117ee5d5c4089

Smart Schedule Encoding Complete: - 264 XOR'd bytes

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (up): p0 :234be85f3db6ee07
          p1 :05542a27169c39e2              p1 :444afaba1846e41c
          p2 :2eab49560bb0b8b4              p2 :63380598287cc9f1
D1  (up): p0 :0bd068c93e5d224d    C1  (up): p0 :3ce17f27632128d2
          p1 :436c8d9c3a2adfda              p1 :007b83bc3127b530
          p2 :1dd8ca796a67c4f1              p2 :58848e25583625c3
D2  (up): p0 :7742fa2948b62d69    C2  (up): p0 :3f859cc07de665ce
          p1 :472e195d0681a900              p1 :0209debd05f7fd02
          p2 :622ebb7e026bccdf              p2 :0d9b22b50721e383
                                  C3  (up): p0 :717233e940cd1381
                                            p1 :6bf70d0a39e15986
                                            p2 :373117ee5d5c4089

Erased 4 random devices:

Data                                Coding
D0  (up  ): p0 :0000000000204a16    C0  (up  ): p0 :234be85f3db6ee07
            p1 :05542a27169c39e2                p1 :444afaba1846e41c
            p2 :2eab49560bb0b8b4                p2 :63380598287cc9f1
D1  (down): p0 :0000000000000000    C1  (down): p0 :0000000000000000
            p1 :0000000000000000                p1 :0000000000000000
            p2 :0000000000000000                p2 :0000000000000000
D2  (down): p0 :0000000000000000    C2  (down): p0 :0000000000000000
            p1 :0000000000000000                p1 :0000000000000000
            p2 :0000000000000000                p2 :0000000000000000
                                    C3  (up  ): p0 :717233e940cd1381
                                                p1 :6bf70d0a39e15986
                                                p2 :373117ee5d5c4089

Decoded using a smart schedule - 272 XOR'd bytes

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (up): p0 :234be85f3db6ee07
          p1 :05542a27169c39e2              p1 :444afaba1846e41c
          p2 :2eab49560bb0b8b4              p2 :63380598287cc9f1
D1  (up): p0 :0bd068c93e5d224d    C1  (up): p0 :3ce17f27632128d2
          p1 :436c8d9c3a2adfda              p1 :007b83bc3127b530
          p2 :1dd8ca796a67c4f1              p2 :58848e25583625c3
D2  (up): p0 :7742fa2948b62d69    C2  (up): p0 :3f859cc07de665ce
          p1 :472e195d0681a900              p1 :0209debd05f7fd02
          p2 :622ebb7e026bccdf              p2 :0d9b22b50721e383
                                  C3  (up): p0 :717233e940cd1381
                                            p1 :6bf70d0a39e15986
                                            p2 :373117ee5d5c4089

Erased the same 4 devices:

Data                                Coding
D0  (up  ): p0 :0000000000204a16    C0  (up  ): p0 :234be85f3db6ee07
            p1 :05542a27169c39e2                p1 :444afaba1846e41c
            p2 :2eab49560bb0b8b4                p2 :63380598287cc9f1
D1  (down): p0 :0000000000000000    C1  (down): p0 :0000000000000000
            p1 :0000000000000000                p1 :0000000000000000
            p2 :0000000000000000                p2 :0000000000000000
D2  (down): p0 :0000000000000000    C2  (down): p0 :0000000000000000
            p1 :0000000000000000                p1 :0000000000000000
            p2 :0000000000000000                p2 :0000000000000000
                                    C3  (up  ): p0 :717233e940cd1381
                                                p1 :6bf70d0a39e15986
                                                p2 :373117ee5d5c4089

Decoded using a dumb schedule - 352 XOR'd bytes

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (up): p0 :234be85f3db6ee07
          p1 :05542a27169c39e2              p1 :444afaba1846e41c
          p2 :2eab49560bb0b8b4              p2 :63380598287cc9f1
D1  (up): p0 :0bd068c93e5d224d    C1  (up): p0 :3ce17f27632128d2
          p1 :436c8d9c3a2adfda              p1 :007b83bc3127b530
          p2 :1dd8ca796a67c4f1              p2 :58848e25583625c3
D2  (up): p0 :7742fa2948b62d69    C2  (up): p0 :3f859cc07de665ce
          p1 :472e195d0681a900              p1 :0209debd05f7fd02
          p2 :622ebb7e026bccdf              p2 :0d9b22b50721e383
                                  C3  (up): p0 :717233e940cd1381
                                            p1 :6bf70d0a39e15986
                                            p2 :373117ee5d5c4089

UNIX>
\end{verbatim}}
This demonstrates usage of
{\bf CRS\_\-Generator()}, 
{\bf CRS\_\-Convert\_\-To\_\-Bitmatrix()},
{\bf JER\_\-Matrix::Print()},
{\bf JER\_\-Slices::Create\_\-Encode\_\-Schedule()},
{\bf JER\_\-Slices::Encode()},
{\bf JER\_\-Slices::Add\_\-Drive\_\-Failure()}, and
{\bf JER\_\-Slices::Decode\_\-Schedule\_\-Lazy()}.

\item {\bf reed\_sol\_crs\_04.cpp}: This takes two parameters: $n$ and $w$.  It calls
{\bf CRS\_N\_Ones()} to determine the number of ones in the bit-matrix representation
of~$n$ in~$GF(2^w)$.  Then it converts~$n$ to a bit-matrix, prints it and confirms the
number of ones:
{\footnotesize \begin{verbatim}
UNIX> reed_sol_crs_04 1 5
# Ones: 5

Bitmatrix has 5 ones

10000
01000
00100
00010
00001

UNIX> reed_sol_crs_04 31 5
# Ones: 16

Bitmatrix has 16 ones

11110
11111
10001
11000
11100
UNIX> 
\end{verbatim}}
% :s/_/\\-\\_/g

This demonstrates usage of 
{\bf JER\_\-Matrix::Set()},
{\bf JER\_\-Matrix::Matrix\_\-To\_\-Bitmatrix()},
{\bf JER\_\-Matrix::Get()},
{\bf CRS\_\-N\_\-Ones()}, and
{\bf JER\_\-Matrix::Print()}.

\item {\bf reed\_sol\_crs\_05.cpp}: This takes three parameters: $k$, $m$ and $w$.  (In this and the
following examples, {\em packetsize} is {\bf 8}.)  It calls
{\bf CRS\_\-Generator()} to create an Cauchy matrix, converts
it to a bit-matrix then encodes and decodes with it.  Smart scheduling is employed.
Lastly, it uses {\bf CRS\_\-XY\_\-Generator()} to create the same Cauchy matrix.  It 
verifies that the two matrices are indeed identical.

Example:
{\footnotesize \begin{verbatim}
UNIX> reed_sol_crs_05 3 3 3
The generator matrix has 46 ones:
6 7 2
5 2 7
1 3 4

Original data:

Data                              Coding
D0  (up): p0 :15ddb16e5ffcc9c0    C0  (down): p0 :0000000000000000
          p1 :0c55e80a6f6b6791                p1 :0000000000000000
          p2 :49e514d0649511f2                p2 :0000000000000000
D1  (up): p0 :5899d1692f33bbae    C1  (down): p0 :0000000000000000
          p1 :6fdc16ba5f5f46b4                p1 :0000000000000000
          p2 :391808482d46f73b                p2 :0000000000000000
D2  (up): p0 :5dc3340b214ef45c    C2  (down): p0 :0000000000000000
          p1 :327837ea636dda66                p1 :0000000000000000
          p2 :6c2a1c8349b36d81                p2 :0000000000000000

Smart Schedule Encoding Complete: - 224 XOR'd bytes

Data                              Coding
D0  (up): p0 :15ddb16e5ffcc9c0    C0  (up): p0 :27c72fc21f6711c3
          p1 :0c55e80a6f6b6791              p1 :70f8a08577598c22
          p2 :49e514d0649511f2              p2 :5550bd8d470398df
D1  (up): p0 :5899d1692f33bbae    C1  (up): p0 :23014e4e16411ad1
          p1 :6fdc16ba5f5f46b4              p1 :75a7f9fa47aea93b
          p2 :391808482d46f73b              p2 :15baa4354280a14e
D2  (up): p0 :5dc3340b214ef45c    C2  (up): p0 :46245fa53ee45f33
          p1 :327837ea636dda66              p1 :5c5a0cf8189fda57
          p2 :6c2a1c8349b36d81              p2 :2ec822aa7e7139a0

Erased 3 random devices:

Data                                Coding
D0  (up  ): p0 :15ddb16e5ffcc9c0    C0  (up  ): p0 :27c72fc21f6711c3
            p1 :0c55e80a6f6b6791                p1 :70f8a08577598c22
            p2 :49e514d0649511f2                p2 :5550bd8d470398df
D1  (up  ): p0 :5899d1692f33bbae    C1  (down): p0 :0000000000000000
            p1 :6fdc16ba5f5f46b4                p1 :0000000000000000
            p2 :391808482d46f73b                p2 :0000000000000000
D2  (down): p0 :0000000000000000    C2  (down): p0 :0000000000000000
            p1 :0000000000000000                p1 :0000000000000000
            p2 :0000000000000000                p2 :0000000000000000

Decode (lazily) with a smart schedule: 192 XOR'd bytes

Data                              Coding
D0  (up): p0 :15ddb16e5ffcc9c0    C0  (up): p0 :27c72fc21f6711c3
          p1 :0c55e80a6f6b6791              p1 :70f8a08577598c22
          p2 :49e514d0649511f2              p2 :5550bd8d470398df
D1  (up): p0 :5899d1692f33bbae    C1  (up): p0 :23014e4e16411ad1
          p1 :6fdc16ba5f5f46b4              p1 :75a7f9fa47aea93b
          p2 :391808482d46f73b              p2 :15baa4354280a14e
D2  (up): p0 :5dc3340b214ef45c    C2  (up): p0 :46245fa53ee45f33
          p1 :327837ea636dda66              p1 :5c5a0cf8189fda57
          p2 :6c2a1c8349b36d81              p2 :2ec822aa7e7139a0

Generated the identical matrix using cauchy_xy_coding_matrix()

UNIX> 
\end{verbatim}}
This demonstrates usage of 
{\bf CRS\_\-Generator()},
{\bf CRS\_\-N\_\-Ones()},
{\bf JER\_\-Matrix::Print()},
{\bf JER\_\-Gen\_\-T::Genmatrix\_\-To\_\-Genbitmatrix()},
{\bf JER\_\-Gen\_\-T()::Create\_\-Encode\_\-Schedule()},
{\bf JER\_\-Slices::Encode()},
{\bf JER\_\-Slices::Decode\_\-Schedule\_\-Lazy()},
{\bf CRS\_\-XY\_\-Generator()}, and
{\bf JER\_\-Matrix::Get()}.

\item {\bf reed\_sol\_crs\_06.cpp}: This example differs from {\bf cauchy\_05.cpp} in two ways. First, {\bf cauchy\_06.cpp} improves the matrix with {\bf CRS\_\-Improve\_\-Generator()}. Secondly, this does not use {\bf CRS\_\-XY\_\-Generator()} to check that the matrices are identical.

Example:
{\footnotesize \begin{verbatim}
UNIX> reed_sol_crs_06 3 3 3 | head -n 10
The generator matrix has 46 ones:
6 7 2
5 2 7
1 3 4

The improved generator matrix has 34 ones:
1 1 1
5 1 2
1 4 7

UNIX> 
\end{verbatim}}
This demonstrates usage of 
{\bf CRS\_\-Generator()},
{\bf CRS\_\-N\_\-Ones()},
{\bf JER\_\-Matrix::Get()},
{\bf JER\_\-Matrix::Print()},
{\bf CRS\_\-Improve\_\-Generator()},
{\bf JER\_\-Gen\_\-T::Genmatrix\_\-To\_\-Genbitmatrix()},
{\bf JER\_\-Gen\_\-T()::Create\_\-Encode\_\-Schedule()},
{\bf JER\_\-Slices::Encode()}, and
{\bf JER\_\-Slices::Decode\_\-Schedule\_\-Lazy()}.

\item {\bf reed\_sol\_crs\_07.cpp}: This is identical to the previous two, except
it calls {\bf CRS\_\-Good\_\-Generator\_\-Bitmatrix()}. Note, 
when~$m = 2$, $w \le 11$ and~$k \le 1023$, these are optimal Cauchy encoding
matrices.  That's not to say that they are optimal RAID-6 matrices (RDP encoding~\cite{ceg:04:rdp},
and Liberation encoding~\cite{p:08:lib} achieve this), but they are the best Cauchy matrices.

{\footnotesize \begin{verbatim}
UNIX> reed_sol_crs_07 10 2 8 | head -n 4
Matrix has 229 ones

  1   1   1   1   1   1   1   1   1   1
  1   2 142   4  71   8  70 173   3  35

UNIX>

UNIX> reed_sol_crs_06 10 2 8 | head -n 8
The generator matrix has 608 ones:
142 244  71 167 122 186 173 157 221 152
244 142 167  71 186 122 157 173 152 221

The improved generator matrix has 354 ones:
  1   1   1   1   1   1   1   1   1   1
 82 200 151 172   1 225 166 158  44  13

UNIX>

UNIX> reed_sol_crs_05 10 2 8 | head -n 4
Matrix has 608 ones

142 244  71 167 122 186 173 157 221 152
244 142 167  71 186 122 157 173 152 221

UNIX> 
\end{verbatim}}
This demonstrates usage of 
{\bf CRS\_\-Good\_\-Generator\_\-Bitmatrix()},
{\bf JER\_\-Gen\_\-T()::Bitmatrix\_\-To\_\-Matrix()},
{\bf JER\_\-Matrix::Get()},
{\bf JER\_\-Matrix::Print()},
{\bf JER\_\-Gen\_\-T()::Create\_\-Encode\_\-Schedule()},
{\bf JER\_\-Slices::Encode()}, and
{\bf JER\_\-Slices::Decode\_\-Schedule\_\-Lazy()}.
\end{itemize}

\section{Part 4 of the Library: Bitmatrix-based Coding (bitmatrices.h)}
\label{src:lib}

The {\bf bitmatrices.h} file contains code to create three types of generator matrices: generalized EVENODD, generalized RDP, and mimal density RAID-6. All of these generators have {\bf PDrive} = {\em true} and {\bf Systematic} = {\em true}.

Minimal Density RAID-6 codes are MDS codes based on binary matrices which satisfy a lower-bound on the number of non-zero entries. Unlike Cauchy coding, the bit-matrix elements do not correspond to elements in~$GF(2^w)$.  Instead, the bit-matrix itself has the proper MDS property. Minimal Density RAID-6 codes perform faster than Reed-Solomon and Cauchy Reed-Solomon codes for the same parameters. Liberation coding, Liber8tion coding, and Blaum-Roth coding are three examples of this kind of coding that are supported in {\bf jerasure}. Note that since these codes are RAID-6,~$m$ must be 2.

Each coding method places restrictions on the values of k and w. The rules are listed below:
\begin{itemize}
\item generalized EVENODD - w+1 is prime, k $\le$ w+1
\item generalized RDP - w+1 is prime, k $\le$ w
\item Blaum-Roth - w+1 is prime, k $\le$ w~\cite{br:99:old}
\item Liber8tion - w == 8, k $\le$ w~\cite{p:08:md8}
\item Liberation - w is prime, k $\le$ w~\cite{p:08:lib}
\end{itemize}

\subsection{EVENODD, RDP, and minimal density RAID-6 generators - bitmatrices.cpp}

The functions found in bitmatrices.cpp are as follows:
\begin{itemize}
\item{\bf int R6\_Min\_Density\_Smallest\_W(int k)}: Given {\bf k}, this returns the smallest {\em w} that is a valid value for a minimal density RAID 6 code (Liberation, Blaum-Roth, or Liber8tion).
\item{\bf int Gen\_Evenodd\_Smallest\_W(int k, int m)}: Given {\bf k} and {\bf m}, this returns the smallest legal {\em w} for a generalized EVENODD algorithm.
\item{\bf JER\_Gen\_T *R6\_Min\_Density\_Generator(int k, int w)}: This function creates and returns a {\bf JER\_Gen\_T} object containing a minimal density matrix. The type of minimal density coding matrix, dependent upon {\bf w}, is either Blaum-Roth, Liberation, or Liber8tion. Returns NULL on failure.
\item{\bf int R6\_Min\_Density\_Generator(int k, int w, JER\_Gen\_T \&g)}: This modifies an existing {\bf JER\_Gen\_T} object, {\bf g}, to contain a minimal density matrix. A new {\bf JER\_Matrix} object is created if the generator's matrix is NULL. Otherwise, the existing matrix is resized and transformed appropriately. Any schedules in the generator's {\bf Schedules} map are deleted with a call to {\bf Delete\_Schedules()}. Returns 0 on success, -1 on failure.
\item{\bf JER\_Gen\_T *Gen\_Evenodd\_Generator(int k, int m, int w)}: Creates and returns a generator object containing a generalized EVENODD matrix. Returns NULL on failure.
\item{\bf int Gen\_Evenodd\_Generator(int k, int m, int w, JER\_Gen\_T \&g)}: Modifies {\bf g} to be a generator object containing a generalized EVENODD matrix. Returns 0 on success, -1 on failure.
\item{\bf JER\_Gen\_T *Gen\_RDP\_Generator(int k, int m, int w)}: Creates and returns a generator object containing a generalized RDP matrix. Returns NULL on failure.
\item{\bf int Gen\_RDP\_Generator(int k, int m, int w, JER\_Gen\_T \&g)}: Modifies {\bf g} to be a generator object containing a generalized RDP matrix. Returns 0 on success, -1 on failure.
\end{itemize}

\subsection{Example programs}

\noindent {\bf bitmatrices\_\-min\_\-den\_\-r6\_\-01.cpp}: This takes two parameters: $k$ and $w$, where~$w$
should be a prime number greater than two and~$k$ must be less than or equal to~$w$.
As in other examples, {\em packetsize} is {\bf 8}.  It sets up a minimal density bit-matrix and uses it for encoding and decoding.
It then encodes by converting the bit-matrix
to a dumb schedule.  The dumb schedule is used because that schedule cannot be improved
upon.  For decoding, smart scheduling is used as it gives a big savings over dumb
scheduling.

{\footnotesize \begin{verbatim}
UNIX> bitmatrices_min_den_r6_01 3 7
Coding Bit-Matrix:

1000000 1000000 1000000
0100000 0100000 0100000
0010000 0010000 0010000
0001000 0001000 0001000
0000100 0000100 0000100
0000010 0000010 0000010
0000001 0000001 0000001

1000000 0100000 0010000
0100000 0010000 0001000
0010000 0001000 0000100
0001000 0001100 0000010
0000100 0000010 0000001
0000010 0000001 1000000
0000001 1000000 1100000


Original data:

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (down): p0 :0000000000000000
          p1 :05542a27169c39e2                p1 :0000000000000000
          p2 :2eab49560bb0b8b4                p2 :0000000000000000
          p3 :0bd068c93e5d224d                p3 :0000000000000000
          p4 :436c8d9c3a2adfda                p4 :0000000000000000
          p5 :1dd8ca796a67c4f1                p5 :0000000000000000
          p6 :7742fa2948b62d69                p6 :0000000000000000
D1  (up): p0 :472e195d0681a900    C1  (down): p0 :0000000000000000
          p1 :622ebb7e026bccdf                p1 :0000000000000000
          p2 :204d531e262b5331                p2 :0000000000000000
          p3 :7020241c440a0e2a                p3 :0000000000000000
          p4 :75cb1c4c41f9a5e1                p4 :0000000000000000
          p5 :67bc26ff181e279e                p5 :0000000000000000
          p6 :7172c06f4909e153                p6 :0000000000000000
D2  (up): p0 :09d3bfba685ae502    
          p1 :7e10e8ab0f262618    
          p2 :726b82306469f5c5    
          p3 :0cead30e206c7b8a    
          p4 :028a2bec306eac4e    
          p5 :56e5747a57287c72    
          p6 :6058b11e00cc2071    

Dumb Schedule Encoding Complete: - 240 XOR'd bytes

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (up): p0 :4efda6e76efb0614
          p1 :05542a27169c39e2              p1 :196a79f21bd1d325
          p2 :2eab49560bb0b8b4              p2 :7c8d987849f21e40
          p3 :0bd068c93e5d224d              p3 :771a9fdb5a3b57ed
          p4 :436c8d9c3a2adfda              p4 :342dba3c4bbdd675
          p5 :1dd8ca796a67c4f1              p5 :2c8198fc25519f1d
          p6 :7742fa2948b62d69              p6 :66688b580173ec4b
D1  (up): p0 :472e195d0681a900    C1  (up): p0 :1045394e6622730c
          p1 :622ebb7e026bccdf              p1 :29f3aa3710db1159
          p2 :204d531e262b5331              p2 :5c0146a67fd41ad0
          p3 :7020241c440a0e2a              p3 :58de24e36c86f5f4
          p4 :75cb1c4c41f9a5e1              p4 :44881a7d22f8d835
          p5 :67bc26ff181e279e              p5 :6579b5ac4b34c0a0
          p6 :7172c06f4909e153              p6 :47afb465294b4773
D2  (up): p0 :09d3bfba685ae502    
          p1 :7e10e8ab0f262618    
          p2 :726b82306469f5c5    
          p3 :0cead30e206c7b8a    
          p4 :028a2bec306eac4e    
          p5 :56e5747a57287c72    
          p6 :6058b11e00cc2071    

Erased 2 random devices:

Data                                Coding
D0  (down): p0 :0000000000000000    C0  (up  ): p0 :4efda6e76efb0614
            p1 :0000000000000000                p1 :196a79f21bd1d325
            p2 :0000000000000000                p2 :7c8d987849f21e40
            p3 :0000000000000000                p3 :771a9fdb5a3b57ed
            p4 :0000000000000000                p4 :342dba3c4bbdd675
            p5 :0000000000000000                p5 :2c8198fc25519f1d
            p6 :0000000000000000                p6 :66688b580173ec4b
D1  (up  ): p0 :472e195d0681a900    C1  (down): p0 :0000000000000000
            p1 :622ebb7e026bccdf                p1 :0000000000000000
            p2 :204d531e262b5331                p2 :0000000000000000
            p3 :7020241c440a0e2a                p3 :0000000000000000
            p4 :75cb1c4c41f9a5e1                p4 :0000000000000000
            p5 :67bc26ff181e279e                p5 :0000000000000000
            p6 :7172c06f4909e153                p6 :0000000000000000
D2  (up  ): p0 :09d3bfba685ae502    
            p1 :7e10e8ab0f262618    
            p2 :726b82306469f5c5    
            p3 :0cead30e206c7b8a    
            p4 :028a2bec306eac4e    
            p5 :56e5747a57287c72    
            p6 :6058b11e00cc2071    

Decode (lazily) with a smart schedule: 240 XOR'd bytes

Data                              Coding
D0  (up): p0 :0000000000204a16    C0  (up): p0 :4efda6e76efb0614
          p1 :05542a27169c39e2              p1 :196a79f21bd1d325
          p2 :2eab49560bb0b8b4              p2 :7c8d987849f21e40
          p3 :0bd068c93e5d224d              p3 :771a9fdb5a3b57ed
          p4 :436c8d9c3a2adfda              p4 :342dba3c4bbdd675
          p5 :1dd8ca796a67c4f1              p5 :2c8198fc25519f1d
          p6 :7742fa2948b62d69              p6 :66688b580173ec4b
D1  (up): p0 :472e195d0681a900    C1  (up): p0 :1045394e6622730c
          p1 :622ebb7e026bccdf              p1 :29f3aa3710db1159
          p2 :204d531e262b5331              p2 :5c0146a67fd41ad0
          p3 :7020241c440a0e2a              p3 :58de24e36c86f5f4
          p4 :75cb1c4c41f9a5e1              p4 :44881a7d22f8d835
          p5 :67bc26ff181e279e              p5 :6579b5ac4b34c0a0
          p6 :7172c06f4909e153              p6 :47afb465294b4773
D2  (up): p0 :09d3bfba685ae502    
          p1 :7e10e8ab0f262618    
          p2 :726b82306469f5c5    
          p3 :0cead30e206c7b8a    
          p4 :028a2bec306eac4e    
          p5 :56e5747a57287c72    
          p6 :6058b11e00cc2071    

UNIX> 
\end{verbatim}}
This demonstrates usage of 
{\bf liberation\-\_coding\-\_bitmatrix()},
{\bf jerasure\-\_dumb\-\_bitmatrix\-\_to\-\_schedule()},
{\bf jerasure\-\_schedule\-\_encode()},
{\bf jerasure\-\_schedule\-\_decode\-\_lazy()},
{\bf jerasure\-\_print\-\_bitmatrix()} and
{\bf jerasure\-\_get\-\_stats()}.

\section{Example Application 1: Encoder and Decoder}
The programs {\bf encoder} and {\bf decoder} are used to encode and decode a single file.
When the file is encoded, it is split into {\bf N} new files. {\bf K} of these new files represent data slices, and {\bf M} represent coding slices. The {\bf decoder} can reconstruct the original file if {\bf K} or more 
of the new files are not deleted.
\subsection{Encoder - encoder.cpp}
This program is used to encode a file using any of the available methods in {\bf Jerasure}.  
It takes seven parameters: 
\begin{itemize}
	\item {\bf inputfile} or negative number $S$: either the file to be encoded 
	or a negative number $S$ indicating that a random file of size $-S$ should 
	be used rather than an existing file
	\item {\bf K}: number of data files
	\item {\bf M}: number of coding files
	\item {\bf coding\_technique}: must be one of the following:
	\begin{itemize}
		\item {\em no\_coding}
		\item {\em reed\-\_sol\-\_van}: calls {\bf RS\_\-Classic\_\-Generator()}
		\item {\em reed\-\_sol\-\_r6\-\_op}: calls {\bf RS\_\-R6\_\-Generator()}
		\item {\em cauchy\-\_orig}: calls {\bf CRS\_\-Generator()}, {\bf CRS\_\-Convert\_\-To\_\-Bitmatrix()}, and {\bf JER\_\-Gen\_\-T::Create\_\-Encode\_\-Schedule(smart = {\em true})}
		\item {\em cauchy\-\_good}: calls {\bf CRS\_\-Good\_\-Generator\_\-Bitmatrix()} and {\bf JER\_\-Gen\_\-T::Create\_\-Encode\_\-Schedule(smart = {\em true})}
		\item {\em r6\_\-min\_\-density}: calls {\bf R6\_\-Min\_\-Density\_\-Generator()} and {\bf JER\_\-Gen\_\-T::Create\_\-Encode\_\-Schedule(smart = {\em true})}
		\item {\em gen\_\-rdp}: calls {\bf Gen\_\-RDP\_\-Generator()}
		\item {\em gen\_\-evenodd}: calls {\bf Gen\_\-Evenodd\_\-Generator()}
	\end{itemize}
	\item {\bf W}: word size
	\item ({\bf packetsize}): For non-bitmatrix based encoding methods, this argument is ignored and set equal to the size of one slice. Therefore, for non-bitmatrix based coding methods, {\bf PacketsPerSlice} is one. For bitmatrix-based coding methods, this must be a multiple of 8.
	\item ({\bf buffersize}): This is the approximate size of data (in bytes) to be read in at a time. It is adjusted to be a multiple of ({\bf K} * {\bf W} * {\bf packetsize}). {\bf Buffersize} is an optional parameter. If it is not given, or it is set to 0, the entire file is read in at once.
\end{itemize}
Encoder reads in {\bf inputfile} (or creates random data), breaks the file
into {\bf K} blocks, and encodes the file into {\bf M} blocks.  It also creates
a metadata file to be used for decoding purposes. It writes all of these into a
directory named {\em Coding}. The output of this program
is the rate of encoding
and the total rate of running of the program,
both given in MB/sec.

{\footnotesize \begin{verbatim}
UNIX> ls -l Movie.wmv
-rwxr-xr-x   1 plank  plank  55211097 Aug 14 10:52 Movie.wmv
UNIX> encoder Movie.wmv 6 2 r6_min_density 7 1024 500000
Encoding (MB/sec): 1405.3442614500
En_Total (MB/sec): 5.8234765527
UNIX> ls -l Coding
total 143816
-rw-r--r--   1 plank  plank  9203712 Aug 14 10:54 Movie_k1.wmv
-rw-r--r--   1 plank  plank  9203712 Aug 14 10:54 Movie_k2.wmv
-rw-r--r--   1 plank  plank  9203712 Aug 14 10:54 Movie_k3.wmv
-rw-r--r--   1 plank  plank  9203712 Aug 14 10:54 Movie_k4.wmv
-rw-r--r--   1 plank  plank  9203712 Aug 14 10:54 Movie_k5.wmv
-rw-r--r--   1 plank  plank  9203712 Aug 14 10:54 Movie_k6.wmv
-rw-r--r--   1 plank  plank  9203712 Aug 14 10:54 Movie_m1.wmv
-rw-r--r--   1 plank  plank  9203712 Aug 14 10:54 Movie_m2.wmv
-rw-r--r--   1 plank  plank       54 Aug 14 10:54 Movie_meta.txt
UNIX> echo "" | awk '{ print 9203712*6 }'
55222272
UNIX> 
\end{verbatim}}

In the above example a 52.7 MB movie file is broken into six data and two
coding blocks using Liberation codes with {\bf W}$=7$ and {\bf packetsize} $= 1$K.
A buffer of 500000 bytes is specified but {\bf encoder} modifies the
buffersize so that it is a multiple of ({\bf K} * {\bf W} * {\bf packetsize}).  

The new directory, {\bf Coding}, contains the six files {\bf Movie\_k1.wmv} through {\bf Movie\_k6.wmv}
(which are parts of the original file) plus the two encoded files {\bf Movie\_m1.wmv} and {\bf Movie\_m2.wmv}.
Note that the file sizes are multiples of 7 and 1024
as well -- the original file was padded with zeros so that it would encode properly.
The metadata file, {\bf Movie\_meta.txt} contains all information 
relevant to {\bf decoder}.

\subsection{Decoder - decoder.cpp}
This program is used in conjunction with {\bf encoder}
to decode any files remaining after erasures and reconstruct the original file.  The only
parameter for {\bf decoder} is {\bf inputfile}, the original file that was encoded.  
This file does not have to exist; the file name is needed only to find
files created by {\bf encoder}, which should be in the {\em Coding} directory.

After some number of erasures, the program locates the surviving files from {\bf encoder} and recreates the
original file if at least {\bf K} of the files still exist.
The rate of decoding and the total rate of running the program are given as output.

Continuing the previous example, suppose that Movie\_k2.wmv and Movie\_m1.wmv are erased.

{\footnotesize \begin{verbatim}
UNIX> rm Coding/Movie_k1.wmv Coding/Movie_k2.wmv
UNIX> mv Movie.wmv Old-Movie.wmv
UNIX> decoder Movie.wmv
Decoding (MB/sec): 1167.8230894030
De_Total (MB/sec): 16.0071713224

UNIX> ls -l Coding
total 215704
-rw-r--r--   1 plank  plank  55211097 Aug 14 11:02 Movie_decoded.wmv
-rw-r--r--   1 plank  plank   9203712 Aug 14 10:54 Movie_k3.wmv
-rw-r--r--   1 plank  plank   9203712 Aug 14 10:54 Movie_k4.wmv
-rw-r--r--   1 plank  plank   9203712 Aug 14 10:54 Movie_k5.wmv
-rw-r--r--   1 plank  plank   9203712 Aug 14 10:54 Movie_k6.wmv
-rw-r--r--   1 plank  plank   9203712 Aug 14 10:54 Movie_m1.wmv
-rw-r--r--   1 plank  plank   9203712 Aug 14 10:54 Movie_m2.wmv
-rw-r--r--   1 plank  plank        54 Aug 14 10:54 Movie_meta.txt
UNIX> diff Coding/Movie_decoded.wmv Old-Movie.wmv
UNIX> 
\end{verbatim}}

This reads in all of the remaining files and creates {\bf Movie\_decoded.wmv} which,
as shown by the {\bf diff} command, 
is identical to the original {\bf Movie.wmv}.  Note that {\bf decoder} does not recreate the lost
data files -- just the original.
\end{itemize}

\subsection{Judicious selection of buffer and packet sizes}

In our tests, the buffer and packet sizes have as much impact on performance
as the code used.  Initial performance results are in~\cite{sp:08:pc}; however
these will be fleshed out more thoroughly.  To give a compelling example, 
look at the following coding times for a randomly created 256M file
on a MacBook Pro (2.16 GHz processor, 32KB L1 cache, 2MB L2 cache):

{\footnotesize \begin{verbatim}
UNIX> encoder -268435456 6 2 r6_min_density 7 1024 50000000
Encoding (MB/sec): 172.6522847357
En_Total (MB/sec): 141.8509585895
UNIX> encoder -268435456 6 2 r6_min_density 7 1024 5000000
Encoding (MB/sec): 1066.8065148470
En_Total (MB/sec): 526.1761192874
UNIX> encoder -268435456 6 2 r6_min_density 7 10240 5000000
Encoding (MB/sec): 1084.6304288755
En_Total (MB/sec): 555.2568545979
UNIX> encoder -268435456 6 2 r6_min_density 7 102400 5000000
Encoding (MB/sec): 943.4553565388
En_Total (MB/sec): 525.2790538399
UNIX>
\end{verbatim}}

When using these routines, one should pay attention to packet and buffer sizes.

\section{Example Application 2: Personal File Archiving}
\section{Example Application 3: RAID}
The {\bf raid} program is used to demonstrate how Jerasure may be used in order to manage a RAID system. The program reads {\bf K} files of identical size and writes to {\bf N} files the encoding of the original data. The program then randomly creates {\bf M} partial failures and {\bf M} - 2 comeplete disk failures and attempts to recover from these. Because, this problem generates 2 * ( {\bf M} - 1 ) failures, there exist scenarios in which some data loss occurs. However, in most cases, this program demonstrates recovery from both partial and disk failures, even when more than {\bf M} failures are present.

\subsection{raid.cpp}
The program 
//TODO, example

\newpage
\bibliographystyle{alpha} %.
\newcommand{\bibdir}{../References} %.
\newcommand{\bibone}{\bibdir/coding,\bibdir/storage,\bibdir/os,\bibdir/compiler}
\bibliography{\bibone} %.

\end{document}
